Pagini recente » Borderou de evaluare (job #1712596) | Cod sursa (job #2123210) | Cod sursa (job #2195473) | Cod sursa (job #2329605) | Cod sursa (job #2972405)
#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];
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;
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 (int j = 1 ; j <= n ; j++)
if (viz[j] == i)
g << j << " ";
g << '\n';
}
return 0;
}