Pagini recente » Cod sursa (job #2470989) | Cod sursa (job #2246716) | Cod sursa (job #345196) | Cod sursa (job #2249137) | Cod sursa (job #933602)
Cod sursa(job #933602)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define Nmax 100010
#define pb push_back
#define forit(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++ it)
int N, M, X, Y, TopSort[Nmax], SCC[Nmax], CrtSCC;
vector<int> G[Nmax], GT[Nmax];
vector<vector<int> > Comp;
bool Used[Nmax];
void DFS_First(int Node)
{
Used[Node] = 1;
forit(it, G[Node])
if(!Used[*it])
DFS_First(*it);
TopSort[++TopSort[0]] = Node;
}
void DFS_Second(int Node)
{
Used[Node] = 0;
forit(it, GT[Node])
if(Used[*it])
DFS_Second(*it);
SCC[Node] = SCC[0];
}
void Kosaraju()
{
for(int i = 1; i <= N; ++ i)
if(!Used[i])
DFS_First(i);
reverse(TopSort + 1, TopSort + TopSort[0] + 1);
for(int i = 1; i <= N; ++ i)
if(Used[TopSort[i]])
{
SCC[0] ++;
DFS_Second(TopSort[i]);
}
Comp = vector<vector<int> > (SCC[0], vector<int>());
for(int i = 1; i <= N; ++ i) Comp[SCC[i] - 1].pb(i);
printf("%i\n", SCC[0]);
for(int i = 0; i < SCC[0]; ++ i)
{
for(int j = 0; j < Comp[i].size(); ++ j)
printf("%i ", Comp[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i;
scanf("%i %i", &N, &M);
for(i = 1; i <= M; ++ i)
{
scanf("%i %i", &X, &Y);
G[X].pb(Y);
GT[Y].pb(X);
}
Kosaraju();
return 0;
}