# Cod sursa(job #2192879)

Utilizator Data 7 aprilie 2018 16:36:47 Componente tare conexe 100 cpp done Arhiva educationala 1.14 kb
``````#include<stdio.h>
#include<vector>
#define Nmax 100010
using namespace std;

int n, m , viz[Nmax], i , a , b , ctc, S[Nmax], nn, N, j;

vector<int> G[Nmax], T[Nmax], Ctc[Nmax];

void sortaret(int nod)  {
int i, N = G[nod].size();
viz[nod] = 1;

for (i = 0; i < N; i++) {
if (!viz[G[nod][i]]) sortaret(G[nod][i]);
}

S[--nn] = nod ;
}

void dfs(int nod) {
int i, N = T[nod].size();

Ctc[ctc].push_back(nod);
viz[nod] = 0;

for (i = 0; i < N; i++) {
if (viz[T[nod][i]]) dfs(T[nod][i]);
}
}

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", &a, &b);
G[a].push_back(b);
T[b].push_back(a);
}

nn = n + 1 ;
for (i = 1; i <= n; i++) {
if(!viz[i]) sortaret(i);
}

for (i = 1; i <= n; i++) {
if (viz[S[i]]) ctc++, dfs(S[i]);
}

printf("%d\n", ctc);
for (i = 1; i <= ctc; i++) {
N = Ctc[i].size();
for (j = 0; j < N; j++) {
printf("%d ", Ctc[i][j]);
}
printf("\n");
}

return 0 ;
}
``````