Pagini recente » Cod sursa (job #3155308) | Cod sursa (job #2194156) | Cod sursa (job #2093401) | Cod sursa (job #2606813) | Cod sursa (job #2972407)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
stack <int>s;
vector <int>v[100005] , vtr[100005] , sol[100005];
int ctc = 0 , viz[100005] , vecin , x , y , n , m;
void dfs (int nod)
{
viz[nod] = 1;
for (auto vecin : v[nod])
if (viz[vecin] == 0)
dfs (vecin);
s.push (nod);
}
void dfst (int nod , int niv)
{
viz[nod] = niv;
sol[niv].push_back (nod);
for (auto vecin : vtr[nod])
if (viz[vecin] == 1)
dfst (vecin , niv);
}
int main()
{
f >> n >> m;
for (int i = 1 ; i <= m ; i++)
{
f >> x >> y;
v[x].push_back (y);
vtr[y].push_back (x);
}
for (int i = 1 ; i <= n ; i++)
if (viz[i] == 0)
dfs (i);
ctc = 1;
while (!s.empty())
{
int nod = s.top ();
s.pop ();
if (viz[nod] == 1)
ctc++ , dfst (nod , ctc);
}
g << ctc - 1 << '\n';;
for (int i = 2 ; i <= ctc ; i++)
{
for (auto vecin : sol[i])
g << vecin << " ";
g << '\n';
}
return 0;
}