Pagini recente » Cod sursa (job #367106) | Rating Veress Eva (avesserev) | Rating Pirlog Marian Nicolae (nicushor21) | Cod sursa (job #2665915) | Cod sursa (job #3289456)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
vector<int> vec[NMAX], trans[NMAX];
bool vis[NMAX];
vector<vector<int>> comps;
vector<int> stk;
void dfs1(int nod)
{
vis[nod] = 1;
for(auto i : vec[nod])
if(!vis[i])
dfs1(i);
stk.push_back(nod);
}
void dfs2(int nod, vector<int>& comp)
{
vis[nod] = 1;
comp.push_back(nod);
for(auto i : trans[nod])
if(!vis[i])
dfs2(i, comp);
}
int main()
{
int n, m;
fin >> n >> m;
while(m--)
{
int i, j;
fin >> i >> j;
vec[i].push_back(j);
trans[j].push_back(i);
}
for(int i = 1; i <= n; i++)
{
if(!vis[i])
dfs1(i);
}
memset(vis, 0, sizeof(vis));
reverse(stk.begin(), stk.end());
for(auto nod : stk)
{
if(!vis[nod])
{
vector<int> comp;
dfs2(nod, comp);
comps.push_back(comp);
}
}
fout << comps.size() << '\n';
for(auto comp : comps)
{
for(auto nod : comp)
fout << nod << ' ';
fout << '\n';
}
return 0;
}