Pagini recente » Cod sursa (job #302950) | Cod sursa (job #2095403) | Cod sursa (job #1030732) | Cod sursa (job #417032) | Cod sursa (job #1552876)
#include <stdio.h>
#include <vector>
#define MAX 100005
using namespace std;
int n, m, a, b, root[MAX], nr;
vector<int> Gout[MAX], Gin[MAX], L, G[MAX];
bool viz[MAX];
void dfs(int u){
viz[u] = 1;
for(int i = 0; i < Gout[u].size(); i++)
if(!viz[Gout[u][i]])
dfs(Gout[u][i]);
L.push_back(u);
}
void dfsBack(int u, int r){
root[u] = r;
for(int i = 0; i < Gin[u].size(); i++)
if(!root[Gin[u][i]])
dfsBack(Gin[u][i], r);
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d%d", &a, &b);
Gout[a].push_back(b);
Gin[b].push_back(a);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs(i);
for(; L.size(); L.pop_back())
if(!root[L.back()])
dfsBack(L.back(), ++nr);
for(int i = 1; i <= n; i++)
G[root[i]].push_back(i);
printf("%d\n", nr);
for(int i = 1; i <= nr; i++){
for(int j = 0; j < G[i].size(); j++)
printf("%d ", G[i][j]);
printf("\n");
}
return 0;
}