Pagini recente » Cod sursa (job #2699216) | Cod sursa (job #1479101) | Cod sursa (job #1862877) | Cod sursa (job #2136111) | Cod sursa (job #943112)
Cod sursa(job #943112)
#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 ){
viz[nod]=1;
for( unsigned int i = 0 ; i < graf1[nod].size(); i++ )
if(viz[graf1[nod][i]]==0)
dfs1(graf1[nod][i]);
s.push(nod);
}
void dfs2(int nod){
viz[nod]=0;
comp_conexe[nr_comp_conexe].push_back(nod);
for(unsigned int i = 0 ; i < graf2[nod].size() ; i++ )
if(viz[graf2[nod][i]]==1)
dfs2(graf2[nod][i]);
}
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;
}