Pagini recente » Cod sursa (job #1709409) | Cod sursa (job #503655) | Cod sursa (job #634767) | Cod sursa (job #3246385) | Cod sursa (job #2880129)
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector <int> a[100001];
vector <int> b[100001];
int i,j,n,m,v1[100001],v2[100001],k,x,y,ctc[10001],nr;
void dfs1(int p)
{v1[p]=1;
for(int q=0;q<a[p].size();q++)
{if(v1[a[p][q]]==0)
dfs1(a[p][q]);
}
}
void dfs2(int p)
{v2[p]=1;
for(int q=0;q<b[p].size();q++)
{if(v2[b[p][q]]==0)
dfs2(b[p][q]);
}
}
int main()
{f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x].push_back(y);
b[y].push_back(x);
}
for(i=1;i<=n;i++)
{
if(ctc[i]==0)
{for(j=1;j<=n;j++)
v2[j]=v1[j]=0;
dfs1(i);
dfs2(i);
nr++;
for(j=1;j<=n;j++)
if(v2[j]==1&&v1[j]==1)
ctc[j]=nr;
for(j=1;j<=n;j++)
v1[j]=v2[j]=0;
}
}
g<<nr<<'\n';
for(i=1;i<=nr;i++ )
{for(j=1;j<=n;j++)
if(ctc[j]==i)
g<<j<<" ";
g<<'\n';}
}