Pagini recente » Cod sursa (job #1146708) | Cod sursa (job #384482) | Cod sursa (job #543869) | Cod sursa (job #863844) | Cod sursa (job #2842685)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
vector<int>G1[100004];
vector<int>G2[100004];
vector<int>sol[100004];
int a,b,n,m,i,j,ok[100004],viz1[100004],viz2[100004],cnt;
void BFS1(int k)
{
vector<int>::iterator i;
for(i=G1[k].begin();i!=G1[k].end();i++)
{
if(viz1[*i]==0)
{
viz1[*i]=1;
BFS1(*i);
}
}
}
void BFS2(int k)
{
vector<int>::iterator i;
for(i=G2[k].begin();i!=G2[k].end();i++)
{
if(viz2[*i]==0)
{
viz2[*i]=1;
BFS2(*i);
}
}
}
int main()
{
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>a>>b;
G1[a].push_back(b);
G2[b].push_back(a);
}
for(i=1;i<=n;i++)
{
if(ok[i]==0)
{
BFS1(i);
BFS2(i);
cnt++;
}
for(j=1;j<=n;j++)
{
if(viz1[j]==1 && viz2[j]==1)
{
ok[j]=1;
sol[cnt].push_back(j);
}
viz1[j]=0;
viz2[j]=0;
}
}
vector<int>::iterator l;
cout<<cnt;
for(i=1;i<=cnt;i++)
{
cout<<'\n';
for(l=sol[i].begin();l!=sol[i].end();l++)
cout<<*l<<" ";
}
return 0;
}