Pagini recente » Cod sursa (job #2773589) | Cod sursa (job #2049652) | Cod sursa (job #2575341) | Cod sursa (job #1298298) | Cod sursa (job #1455517)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int Dim = 100001;
vector<int> G[Dim], TG[Dim], SCC[Dim];
int N,M,K,Nr;
int F[Dim];
bool V[Dim];
void DFS1(int Node)
{
V[Node] = 1;
for (int i = 0;i < G[Node].size();i++)
if (!V[G[Node][i]])
DFS1(G[Node][i]);
F[++Nr] = Node;
}
void DFS2(int Node)
{
V[Node] = 1;
SCC[K].pb(Node);
for (int i = 0;i < TG[Node].size();i++)
if (!V[TG[Node][i]])
DFS2(TG[Node][i]);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&N,&M);
for (int i = 1;i <= M;i++)
{
int A,B;
scanf("%d%d",&A,&B);
G[A].pb(B);
TG[B].pb(A);
}
for (int i = 1;i <= N;i++)
if (!V[i])
DFS1(i);
memset(V,0,sizeof(V));
for (int i = Nr;i > 0;i--)
if (!V[F[i]])
{
K++;
DFS2(F[i]);
}
printf("%d\n",K);
for (int i = 1;i <= K;i++)
{
for (int j = 0;j < SCC[i].size();j++)
printf("%d ",SCC[i][j]);
printf("\n");
}
return 0;
}