Pagini recente » Cod sursa (job #380595) | Cod sursa (job #1411792) | Cod sursa (job #136071) | Cod sursa (job #1220305) | Cod sursa (job #1265595)
# include <cstdio>
# include <vector>
using namespace std;
vector <int> a[100001],b[100001];
vector<pair<int,int> > v;
int n,m,i,x,y,k;
bool c[100001],d[100001],t[100001];
void DFS1(int x)
{
if(!c[x]&&!t[x])
{
c[x]=1;
int i,m;
m=a[x].size();
for(i=0;i<m;i++)
DFS1(a[x][i]);
}
}
void DFS2(int x)
{
if(!d[x]&&!t[x])
{
d[x]=1;
if(c[x])
{v.push_back(make_pair(x,k));t[x]=1;}
int i,m;
m=b[x].size();
for(i=0;i<m;i++)
DFS2(b[x][i]);
}
}
void ini()
{
int i;
for(i=1;i<=n;i++)
c[i]=d[i]=0;
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
b[y].push_back(x);
}
for(i=1;i<=n;i++)
{
if(!t[i]){
ini();
k++;
//v.push_back(make_pair(i,k));
DFS1(i);
DFS2(i);}
}
printf("%d\n",k);
printf("%d ",v[0].first);
for(i=1;i<v.size();i++)
if(v[i].second==v[i-1].second)
printf("%d ",v[i].first);
else
printf("\n%d ",v[i].first);
return 0;
}