Pagini recente » Cod sursa (job #1560694) | Cod sursa (job #3309658) | Cod sursa (job #1135621) | Cod sursa (job #2193927) | Cod sursa (job #1221217)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[100005],vt[100005],sol[100005];
queue <int> q;
int n,m,use[100005],ok[100005],was[100005],nrc;
int main()
{ int i,j,x,y;
f>>n>>m;
for(i=1;i<=m;i++)
{ f>>x>>y;
v[x].push_back(y);
vt[y].push_back(x);
}
for(i=1;i<=n;i++)
if (!use[i])
{ use[i]=1;
memset(ok,0,sizeof(ok));
memset(was,0,sizeof(was));
q.push(i); was[i]=1;
while(!q.empty())
{ x=q.front(); q.pop();
for(j=0;j<v[x].size();j++)
if (!use[v[x][j]] && !was[v[x][j]])
{ ok[v[x][j]]++;
was[v[x][j]]=1;
q.push(v[x][j]);
}
}
memset(was,0,sizeof(was));
q.push(i); was[i]=1;
while(!q.empty())
{ x=q.front(); q.pop();
for(j=0;j<vt[x].size();j++)
if (!use[vt[x][j]] && !was[vt[x][j]])
{ ok[vt[x][j]]++;
was[vt[x][j]]=1;
q.push(vt[x][j]);
}
}
nrc++; sol[nrc].push_back(i);
for(j=1;j<=n;j++)
if (!use[j] && ok[j]==2)
{ use[j]=1; sol[nrc].push_back(j); }
}
g<<nrc<<"\n";
for(i=1;i<=nrc;i++)
{for(j=0;j<sol[i].size();j++)
g<<sol[i][j]<<" ";
g<<"\n";
}
return 0;
}