Pagini recente » Cod sursa (job #2680113) | Cod sursa (job #481835) | Cod sursa (job #1206003) | Cod sursa (job #1698411) | Cod sursa (job #2398461)
#include <cstdio>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");
int n,m;
vector<int> G1[Nmax],G2[Nmax];
int vizitat[Nmax],vizitat2[Nmax];
vector<vector<int>> ans;
stack<int> q;
vector<int> aux;
void dfs1(int x)
{
q.push(x);
vizitat[x] = 1;
for(int i=0;i<(int)G1[x].size();i++)
if(!vizitat[G1[x][i]])
dfs1(G1[x][i]);
}
void dfs2(int x)
{
aux.push_back(x);
vizitat2[x] =1;
for(int i=0;i<(int)G2[x].size();i++)
if(!vizitat2[G2[x][i]])
dfs2(G2[x][i]);
}
int main()
{
fscanf(f,"%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
fscanf(f,"%d%d",&x,&y);
G1[x].push_back(y);
G2[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!vizitat[i])
dfs1(i);
while(!q.empty())
{
int x=q.top();
q.pop();
if(!vizitat2[x])
{
dfs2(x);
ans.push_back(aux);
aux.clear();
}
}
fprintf(g,"%d",ans.size());
fprintf(g,"\n");
for(int i=0;i<(int)ans.size();i++)
{
for(int j=0;j<(int)ans[i].size();j++)
fprintf(g,"%d ",ans[i][j]);
fprintf(g,"\n");
}
return 0;
}