Pagini recente » Cod sursa (job #2919479) | Cod sursa (job #467081) | Cod sursa (job #1516208) | Cod sursa (job #3144606) | Cod sursa (job #2706227)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax=100000;
vector <int> g[nmax+1];
int low[nmax+1];
bool u[nmax+1], u2[nmax+1];
int ctc=1;
void dfs(int x){
u[x]=1;
for(int i=0;i<int(g[x].size());i++){
int xn=g[x][i];
if(low[x]>low[xn]){
low[x]=low[xn];
dfs(xn);
}
if(u[xn]==0){
dfs(xn);
}
}
}
void dfs2(int x){
u2[x]=1;
for(int i=0;i<int(g[x].size());i++){
int xn=g[x][i];
if(low[x]>low[xn]){
low[x]=low[xn];
}
if(u2[xn]==0){
dfs2(xn);
}
}
}
int main(){
int n,m;
fin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
fin>>x>>y;
g[x].push_back(y);
low[x]=x;
}
for(int i=1;i<=n;i++){
if(u[i]==0){
dfs(i);
}
}
for(int i=1;i<=n;i++){
if(u2[i]==0){
dfs2(i);
}
}
/*
for(int i=1;i<=n;i++){
fout<<i<<" ";
}
fout<<"\n";
for(int i=1;i<=n;i++){
fout<<low[i]<<" ";
}
fout<<"\n\n";
*/
int x=low[1];
for(int i=2;i<=n;i++){
if(x!=low[i]){
x=low[i];
ctc++;
}
}
fout<<ctc<<"\n";
x=low[1];
for(int i=1;i<=n;i++){
if(x!=low[i]){
x=low[i];
fout<<"\n";
}
fout<<i<<" ";
}
return 0;
}