Pagini recente » Cod sursa (job #1086436) | Cod sursa (job #334053) | Cod sursa (job #2519019) | Cod sursa (job #2444320) | Cod sursa (job #1890093)
#include<bits/stdc++.h>
#define N 100020
using namespace std;
vector <int> lda[N], lda1[N];
int t, v[N], c[N], col=0, b=0;
struct p{
int v, ind;
} a[N];
ifstream f("ctc.in");
ofstream g("ctc.out");
void dfs(int nod){
v[nod]=1;
int i;
for(i=0;i<lda[nod].size();i++)if(!v[lda[nod][i]]){
dfs(lda[nod][i]);
}
++t;
a[nod].v=t;
a[nod].ind=nod;
}
void dfs1(int nod){
v[nod]=1;
if(b)g<<nod<<" ";
int i;
for(i=0;i<lda1[nod].size();i++)if(!v[lda1[nod][i]]){
dfs1(lda1[nod][i]);
}
c[nod]=col;
}
int cmp(p a, p b){
return(a.v>b.v);
}
int main(){
int i, n, m, j, x, y;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
lda[x].push_back(y);
lda1[y].push_back(x);
}
for(i=1;i<=n;i++)if(v[i]==0)dfs(i);
sort(a+1, a+n+1, cmp);
for(i=1;i<=n;i++)v[i]=0;
for(i=1;i<=n;i++)if(!v[i]){
col++;
dfs1(i);
}
g<<col<<endl;
b=1;
for(i=1;i<=n;i++)v[i]=0;
for(i=1;i<=n;i++)if(!v[i]){
dfs1(i);
g<<endl;
}
return 0;
}