Pagini recente » Cod sursa (job #1657740) | Cod sursa (job #232857) | Monitorul de evaluare | Cod sursa (job #2032984) | Cod sursa (job #1099532)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int use[100001], st[100001], scos[100001];
int stc=0, nrtc=0;
vector <int> sol[100001];
void dfs(int nod, vector <int> a[]){
use[nod]=1;
st[stc]=nod; stc++;
int i;
for (i=0; i<a[nod].size(); i++){
if (!use[a[nod][i]] && !scos[a[nod][i]]){dfs(a[nod][i], a);}
}
}
void dfs1(int nod, vector <int> t[]){
use[nod]=1;
int i;
for (i=0; i<stc; i++){
if (nod==st[i]){sol[nrtc].push_back(nod); scos[nod]=1;}
}
for (i=0; i<t[nod].size(); i++){
if (!use[t[nod][i]] && !scos[t[nod][i]]){dfs1(t[nod][i], t);}
}
}
int main(){
int n, m, i, j, e1, e2;
ifstream in("ctc.in");
ofstream out("ctc.out");
in>>n>>m;
vector <int> a[n+1];
vector <int> t[n+1];
for (i=1; i<=m; i++){
in>>e1>>e2;
a[e1].push_back(e2);
t[e2].push_back(e1);
}
for (i=1; i<=n; i++){
use[i]=0;
}
for (i=1; i<=n; i++){
scos[i]=0;
}
for (i=1; i<=n; i++){
if (!scos[i]){dfs(i, a);}
for (j=1; j<=n; j++){
use[j]=0;
}
if (!scos[i]){dfs1(i, t); nrtc++;}
stc=0;
}
out<<nrtc;
for (i=0; i<nrtc; i++){
out<<endl;
for (j=0; j<sol[i].size(); j++){
out<<sol[i][j]<<" ";
}
}
return 0;
}