Pagini recente » Cod sursa (job #1551340) | Solutii - Summer Challenge Doi | Solutii - Summer Challenge Doi | Monitorul de evaluare | Cod sursa (job #2010071)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int nmax=1e5+5;
vector<int> g[nmax],gt[nmax],temp;
vector< vector<int> > sol;
bool viz[nmax],viz2[nmax];
stack<int>st;
inline void dfs(int node)
{
viz[node]=1;
int i,cnode;
for(i=0;i<g[node].size();++i)
{
cnode=g[node][i];
if(!viz[cnode])
dfs(cnode);
}
st.push(node);
}
inline void dfs2(int node)
{
viz2[node]=1;
int i,cnode;
for(i=0;i<gt[node].size();++i)
{
cnode=gt[node][i];
if(!viz2[cnode])
dfs2(cnode);
}
temp.push_back(node);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int m,n,i,j;
scanf("%d%d",&n,&m);
int x,y;
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!viz[i])
dfs(i);
int node,cnt=0;
while(!st.empty())
{
node=st.top();
st.pop();
if(!viz2[node])
{
temp.clear();
dfs2(node);
cnt++;
sol.push_back(temp);
}
}
printf("%d\n",cnt);
for(i=0;i<cnt;++i)
{
for(j=0;j<sol[i].size();++j)
printf("%d ",sol[i][j]);
printf("\n");
}
}