Pagini recente » Cod sursa (job #2872156) | Cod sursa (job #1343830) | Cod sursa (job #1604676) | Cod sursa (job #3152611) | Cod sursa (job #443147)
Cod sursa(job #443147)
#include <stdio.h>
#include <vector>
#define Nmax 100005
using namespace std;
int n, m, i, j, x, y, nrc, nr, q;
int S[Nmax];
char viz[Nmax];
vector <int> g[Nmax], t[Nmax], sol[Nmax];
void DFSi (int nod){
int k;
viz[nod] = 1;
S[++q] = nod;
for (k = 0 ; k < (int)g[nod].size() ; k++)
if (viz[g[nod][k]] == 0)
DFSi(g[nod][k]);
}
void DFSj(int nod){
int k;
viz[nod] = 0;
sol[nr].push_back(nod);
for (k = 0 ; k < (int)t[nod].size() ; k++)
if (viz[t[nod][k]] == 1)
DFSj(t[nod][k]);
}
int main (){
freopen ("ctc.in","r", stdin);
freopen ("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1 ; i <= m ; i++){
scanf ("%d %d", &x, &y);
g[x].push_back(y);
t[y].push_back(x);
}
for (i = 1 ; i <= n ; i++)
if (!viz[i])
DFSi(i);
for ( ; q > 0 ; q--)
if (viz[S[q]]){
nr++;
DFSj(S[q]);
}
printf ("%d\n", nr);
for (i = 1 ; i <= nr ; i++){
for (j = 0 ; j < (int)sol[i].size() ; j++)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}