Pagini recente » Cod sursa (job #510508) | Cod sursa (job #1370390) | Cod sursa (job #1965331) | Cod sursa (job #1401592) | Cod sursa (job #2276273)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int const NM = 1e5;
vector <int> v [1 + NM] , comp , v2 [1 + NM];
vector <vector <int>> sol;
bitset <1 + NM> viz;
int stop [1 + NM] , k;
void DF (int node){
viz [node] = 1;
for(auto i : v [node])
if (! viz [i])
DF (i);
stop [++ k] = node;
}
void flood (int node){
viz [node] = 1;
comp . push_back (node);
for(auto i : v2 [node])
if (! viz [i])
flood (i);
}
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])
DF (i);
for(int i = 1 ; i <= n ; ++ i)
viz [i] = 0;
k = 0;
for(int i = n ; i > 0 ; -- i)
if (! viz [stop [i]]){
comp . clear ();
flood (stop [i]);
sol . push_back (comp);
}
g << sol . size () << '\n';
for(auto i : sol){
for(auto j : i)
g << j << ' ';
g << '\n';
}
return 0;
}