Pagini recente » Cod sursa (job #2157184) | Cod sursa (job #2972216) | Cod sursa (job #1241012) | Cod sursa (job #2710484) | Cod sursa (job #943108)
Cod sursa(job #943108)
#include<iostream>
#include<vector>
#include<fstream>
#include<stack>
#define MAX 100000
#define MAX_comp 4000
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> graf1[MAX],graf2[MAX],comp_conexe[MAX];
stack <int> s;
int nr_comp_conexe;
void dfs1(int nod ,int (&viz)[MAX]){
viz[nod]=1;
for( unsigned int i = 0 ; i < graf1[nod].size(); i++ )
if(viz[graf1[nod][i]]==0)
dfs1(graf1[nod][i],viz);
s.push(nod);
}
void dfs2(int nod, int (&viz)[MAX]){
viz[nod]=1;
comp_conexe[nr_comp_conexe].push_back(nod);
for(unsigned int i = 0 ; i < graf2[nod].size() ; i++ )
if(viz[graf2[nod][i]]==0)
dfs2(graf2[nod][i],viz);
}
void tarjan( int (&viz)[MAX] ){
int val;
while(!s.empty()){
val=s.top();
cout<<val<<" ";
s.pop();
if(viz[val]==0){
dfs2(val,viz);
nr_comp_conexe++;
}
}
}
void afisare(){
unsigned int i;
int j;
out<<nr_comp_conexe<<endl;
for( j = 0 ; j < nr_comp_conexe ; j++ ){
for( i = 0; i < comp_conexe[j].size(); i++)
out<<comp_conexe[j][i]<<" ";
out<<endl;
}
}
int main(){
int n,m,x,y,viz[MAX],i;
in>>n>>m;
for( i = 1; i <= m; i++){
in>>x>>y;
graf1[x].push_back(y);
graf2[y].push_back(x);
}
for( i = 1 ; i <= n ; i++)
viz[i]=0;
for(i = 1 ; i <= n ; i++ )
if(viz[i]==0)
dfs1(i,viz);
for( i = 1 ; i <= n ; i++)
viz[i]=0;
tarjan(viz);
afisare();
return 0;
}