Pagini recente » Cod sursa (job #864349) | Cod sursa (job #1466523) | Cod sursa (job #2665773) | Cod sursa (job #306199) | Cod sursa (job #1368218)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> gr[100005],gr2[100005],v[100005];
int n,m,viz[100005],viz2[100005],d[100005],l;
bool v3[100005];
void dfs(int p)
{
int i;
viz[p]=1;
d[p]++;
for(i=0;i<gr[p].size();i++)
{
if(viz[gr[p][i]]==0 && v3[gr[p][i]]==0)
dfs(gr[p][i]);
}
}
void dfs2(int p)
{
int i;
viz2[p]=1;
d[p]--;
for(i=0;i<gr2[p].size();i++)
{
if(viz2[gr2[p][i]]==0 && v3[gr2[p][i]]==0)
dfs2(gr2[p][i]);
}
}
int main()
{
int i,j,x,y;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
gr[x].push_back(y);
gr2[y].push_back(x);
}
for(i=1;i<=n;i++)
{
if(viz[i]==0 && v3[i]==0)
{
dfs(i);
dfs2(i);
l++;
for(j=1;j<=n;j++)
{
if(d[j]==0 && viz[j]==1 && viz2[j]==1)
{
v3[j]=1;
v[l].push_back(j);
}
d[j]=0;
viz[j]=0;
viz2[j]=0;
}
}
}
g<<l;
for(i=1;i<=l;i++)
{
g<<"\n";
for(j=0;j<v[i].size();j++)
g<<v[i][j]<<" ";
}
}