Pagini recente » Cod sursa (job #290148) | Cod sursa (job #388359) | Cod sursa (job #3258919) | Cod sursa (job #1612137) | Cod sursa (job #2210935)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100001
stack<int> S;
vector<int> viz;
vector<int> g[NMAX];
vector<int> gt[NMAX];
void dfs(int nod) {
viz[nod] = 1;
for(int i = 0; i < g[nod].size(); i++) {
if(viz[g[nod][i]] == 0) {
dfs(g[nod][i]);
}
}
S.push(nod);
}
void dfsT(int nod, int flag) {
viz[nod] = flag;
for(int i = 0; i < gt[nod].size(); i++) {
if(viz[gt[nod][i]] == 0) {
dfsT(gt[nod][i], flag);
}
}
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int N, M;
int a, b;
scanf("%d %d", &N, &M);
for(int i = 0; i < M; i++) {
scanf("%d %d", &a, &b);
g[a].push_back(b);
gt[b].push_back(a);
}
viz.resize(N + 1, 0);
for(int i = 1; i <= N; i++) {
if(viz[i] == 0) {
dfs(i);
}
}
viz.assign(N + 1, 0);
int cnt = 0;
int index = 1;
while(!S.empty()) {
int nod = S.top();
S.pop();
if(viz[nod] == 0) {
dfsT(nod, index);
cnt ++;
index ++;
}
}
vector< vector<int> > sol(cnt + 1);
for(int i = 1; i <= N; i ++) {
sol[viz[i]].push_back(i);
}
printf("%d\n", cnt);
for(int i = 1; i <= cnt; i ++) {
for(int j = 0; j < sol[i].size(); j ++) {
printf("%d ", sol[i][j]);
}
printf("\n");
}
return 0;
}