Pagini recente » Cod sursa (job #1476370) | Cod sursa (job #2575687) | Cod sursa (job #2357505) | Cod sursa (job #919108) | Cod sursa (job #2790321)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int const N = 1e5 + 3;
int stop [N];
vector <int> v [N] , v2 [N] , comp;
vector <vector <int> > sol;
bool viz [N];
void dfs (int node){
viz [node] = true;
for(auto y : v [node])
if (! viz [y])
dfs (y);
stop [++ stop [0]] = node;
}
void bf (int start){
queue <int> q;
q.push (start);
viz [start] = 1;
while (q.size ()){
int x = q.front ();
comp.push_back (x);
q.pop ();
for(auto y : v2 [x])
if (! viz [y]){
viz [y] = 1;
q.push (y);
}
}
}
int main()
{
int n , m;
f >> n >> m;
for(int i = 1 ; i <= m ; ++ i){
int a , b;
f >> a >> b;
v [a].push_back (b);
v2 [b].push_back (a);
}
for(int i = 1 ; i <= n ; ++ i)
if (! viz [i])
dfs (i);
fill (viz , viz + n + 1 , false);
for(int i = n ; i > 0 ; -- i)
if (! viz [stop [i]]){
comp.clear ();
bf (stop [i]);
sol.push_back (comp);
}
g << sol.size () << '\n';
for(auto y : sol){
for(auto y2 : y)
g << y2 << ' ';
g << '\n';
}
return 0;
}