Pagini recente » Cod sursa (job #2317402) | Cod sursa (job #1341865) | Cod sursa (job #634952) | Cod sursa (job #2963149) | Cod sursa (job #922909)
Cod sursa(job #922909)
#include <stdio.h>
#include <vector>
using namespace std;
#define Nmax 100005
vector< vector <int> > graf, grafT;
int visited[Nmax], finishOrder[Nmax];
int n, m, c, comp;
void read(){
int x, y;
scanf("%i %i", &n, &m);
graf.resize(n+1);
grafT.resize(n+1);
for(int i = 1; i <= m; ++i){
scanf("%i %i", &x, &y);
graf[x].push_back(y);
grafT[y].push_back(x);
}
fclose(stdin);
}
void dfs(int v){
vector <int>::iterator it;
visited[v] = 1;
for(it = graf[v].begin(); it != graf[v].end(); ++it)
if(!visited[*it])
dfs(*it);
finishOrder[++c] = v;
}
void dfsT(int v){
vector <int>::iterator it;
visited[v] = 0;
for(it = grafT[v].begin(); it != grafT[v].end(); ++it)
if(visited[*it])
dfsT(*it);
}
void dfsTS(int v){
printf("%i ", v);
vector <int>::iterator it;
visited[v] = 1;
for(it = grafT[v].begin(); it != grafT[v].end(); ++it)
if(!visited[*it])
dfsTS(*it);
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read();
for(int i = 1; i <= n ; ++i)
if(!visited[i])
dfs(i);
for(int i = n; i >= 1; --i)
if(visited[ finishOrder[i] ]){
++comp;
dfsT( finishOrder[i] );
}
printf("%i\n", comp);
for(int i = n; i >= 1; --i)
if(!visited[ finishOrder[i] ]){
dfsTS( finishOrder[i] );
printf("\n");
}
}