Pagini recente » Cod sursa (job #2585957) | Cod sursa (job #1756420) | Cod sursa (job #925768) | Cod sursa (job #1615377) | Cod sursa (job #2265253)
#include <bits/stdc++.h>
using namespace std;
#define FILE_IO
namespace Graph
{
int N, M;
int I, idx[100005], low[100005], done[100005];
vector<int> now, edg[100005];
vector< vector<int> > scc;
void addEdge(int x, int y) { edg[x].push_back(y); }
void DFS(int nod)
{
if(idx[nod] || done[nod]) return;
idx[nod] = ++I;
low[nod] = idx[nod];
for(auto nxt: edg[nod])
if(!done[nxt])
{
DFS(nxt);
low[nod] = min(low[nod], low[nxt]);
}
now.push_back(nod);
if(low[nod] == idx[nod])
{
for(auto &x: now) done[x] = 1;
scc.push_back(now);
now.clear();
}
}
void computeSCC()
{
scc.clear();
I = 0;
for(int i = 1; i <= N; i++) low[i] = idx[i] = done[i] = 0;
now.clear();
for(int i = 1; i <= N; i++) DFS(i);
printf("%d\n", scc.size());
for(auto &v: scc)
{
for(auto &x: v) printf("%d ", x);
printf("\n");
}
}
}
int main()
{
#ifdef FILE_IO
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
#endif
using namespace Graph;
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y);
}
computeSCC();
return 0;
}