Pagini recente » Cod sursa (job #1315859) | Cod sursa (job #2219922) | Cod sursa (job #1803873) | Cod sursa (job #165013) | Cod sursa (job #1639961)
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
FILE* f=fopen("ctc.in","r");
FILE* g=fopen("ctc.out","w");
int n,m,qq,qqq,t;
bool viz[100001];
stack <int> st;
vector <int> v[100001];
vector <int> v2[100001];
vector <int> ght[100001];
void dfs1(int x)
{
viz[x]=true;
for(int i=0; i<v[x].size(); i++)
if(!viz[v[x][i]])
dfs1(v[x][i]);
st.push(x);
}
void dfs2(int x)
{
viz[x]=false;
ght[t].push_back(x);
for(int i=0; i<v2[x].size(); i++)
if(viz[v2[x][i]])
dfs2(v2[x][i]);
}
void inv()
{
for(int i=1; i<=n; i++)
for(int j=0; j<v[i].size(); j++)
if(v[v[i][j]].size())
v2[v[i][j]].push_back(i);
}
int main()
{
fscanf(f,"%d%d",&n,&m);
for(int i=0; i<m; i++)
{
fscanf(f,"%d%d",&qq,&qqq);
v[qq].push_back(qqq);
}
for(int i=1; i<=n; i++)
if(!viz[i])
{
dfs1(i);
}
inv();
while(!st.empty())
{
if(viz[st.top()])
dfs2(st.top()),t++;
st.pop();
}
fprintf(g,"%d\n",t);
for(int i=0;i<t;i++)
{
for(int j=ght[i].size()-1;j>=0;j--)
{
fprintf(g,"%d ",ght[i][j]);
}
fprintf(g,"\n");
}
return 0;
}