Pagini recente » Cod sursa (job #2938057) | Cod sursa (job #2792931) | Cod sursa (job #993565) | Cod sursa (job #3166683) | Cod sursa (job #3226565)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int nmax = 2e5 + 7;
vector <int> adj[nmax];
vector <int> cc[nmax];
stack<int>s;
int low[nmax], id[nmax], on_stack[nmax];
int curent_id = 0, ssc = 0;
void dfs(int node)
{
curent_id++;
id[node] = curent_id;
s.push(node);
on_stack[node] = 1;
for(auto next:adj[node])
{
if(id[next] == 0)
dfs(next);
if(on_stack[next])
low[id[node]] = min(low[id[node]], low[id[next]]);
}
if(id[node] == low[id[node]] && on_stack[node] == 1)
{
ssc++;
while(s.top() != node)
{
low[id[s.top()]] = low[id[node]];
on_stack[s.top()] = 0;
s.pop();
}
on_stack[s.top()] = 0;
s.pop();
}
}
int main()
{
int n,m,i;
cin >> n >> m;
for(i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
for(i = 1; i <= n; i++)
low[i] = i;
for(i = 1; i <= n; i++)
if(id[i] == 0)
dfs(i);
cout << ssc << endl;
for(i = 1; i <= n; i++)
cc[low[id[i]]].push_back(i);
for(i = 1; i < nmax; i++)
{
if(cc[i].size())
{
for(auto it:cc[i])
cout << it << " ";
cout << endl;
}
}
return 0;
}