Pagini recente » Cod sursa (job #2559520) | Cod sursa (job #1803099) | Cod sursa (job #952185) | Cod sursa (job #655784) | Cod sursa (job #943116)
Cod sursa(job #943116)
#include<iostream>
#include<vector>
#include<fstream>
#include<stack>
#define MAX 100000
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,viz[MAX];
void dfs1(int nod ){
vector <int > ::iterator it;
viz[nod]=1;
for( it = graf1[nod].begin() ; it < graf1[nod].end(); it++ )
if(viz[*it]==0)
dfs1(*it);
s.push(nod);
}
void dfs2(int nod){
vector <int > ::iterator it;
viz[nod]=0;
comp_conexe[nr_comp_conexe].push_back(nod);
for( it = graf2[nod].begin() ; it < graf2[nod].end(); it++ )
if(viz[*it]==1)
dfs2(*it);
}
void tarjan( ){
int val;
while(!s.empty()){
if(viz[s.top()]==1){
dfs2(s.top());
nr_comp_conexe++;
}
s.pop();
}
}
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,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++ )
if(viz[i]==0)
dfs1(i);
tarjan();
afisare();
return 0;
}