Pagini recente » Cod sursa (job #2965780) | Cod sursa (job #3191071) | Cod sursa (job #2895572) | Cod sursa (job #2709636) | Cod sursa (job #3296324)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
string filename = "";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int NMAX = 1e5;
vector<int> adj[NMAX + 5],gt[NMAX + 5];
vector<int> postordine;
int nr;
vector<int> ctc[NMAX + 5];
bool visited[NMAX + 5];
void dfs(int nod)
{
visited[nod] = true;
for(auto it : adj[nod])
if(!visited[it])
dfs(it);
postordine.push_back(nod);
}
void dfst(int nod)
{
visited[nod] = true;
for(auto it : gt[nod])
if(!visited[it])
dfst(it);
ctc[nr].push_back(nod);
}
int main()
{
int n,m;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
fin>>u>>v;
adj[u].push_back(v);
gt[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(!visited[i])
dfs(i);
}
for(int i=1;i<=n;i++)
visited[i]=false;
reverse(postordine.begin(),postordine.end());
for(auto it : postordine)
{
if(!visited[it])
{
nr++;
dfst(it);
}
}
fout<<nr<<'\n';
for(int i=1;i<=nr;i++)
{
for(auto it : ctc[i])
fout<<it<<' ';
fout<<'\n';
}
return 0;
}