Pagini recente » Cod sursa (job #2269084) | Cod sursa (job #2887679) | Borderou de evaluare (job #1105280) | Cod sursa (job #2129185) | Cod sursa (job #943117)
Cod sursa(job #943117)
#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(){
vector <int > ::iterator it;
unsigned int i;
int j;
out<<nr_comp_conexe<<endl;
for( j = 0 ; j < nr_comp_conexe ; j++ ){
for( it = comp_conexe[j].begin() ; it < comp_conexe[j].end(); it++)
out<<*it<<" ";
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;
}