Pagini recente » Cod sursa (job #2739388) | Cod sursa (job #3179395) | Cod sursa (job #66230) | Cod sursa (job #3163907) | Cod sursa (job #2760186)
#include <bits/stdc++.h>
#define nmax (int)1e5+1
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> dfs;
vector<int> adj[nmax];
vector<int> adjRev[nmax];
vector<bool> visited(nmax);
vector<int> ans[nmax];
void runDfsRev(int nod)
{
if(visited[nod]) return;
visited[nod]=1;
for(auto next:adjRev[nod])
{
runDfsRev(next);
}
dfs.push_back(nod);
}
void runDfs(int nod,vector<int> *ans)
{
if(visited[nod]) return;
visited[nod]=1;
for(auto next:adj[nod])
{
runDfs(next,ans);
}
ans->push_back(nod);
}
int main()
{
int n,m,k=0;
f>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
f>>a>>b;
adj[a].push_back(b);
adjRev[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(!visited[i]) runDfsRev(i);
}
//for(auto e:dfs) cout<<e<<' ';
for(int i=1;i<=n;i++) visited[i]=0;
for(int i=dfs.size()-1;i>=0;i--)
{
if(!visited[dfs[i]])
{
k++;
runDfs(dfs[i],&ans[k]);
}
}
g<<k<<'\n';
for(int i=1;i<=k;i++)
{
for(auto e:ans[i])
{
g<<e<<' ';
}
g<<'\n';
}
f.close();
g.close();
return 0;
}