Pagini recente » Cod sursa (job #1050782) | Cod sursa (job #2301295) | Cod sursa (job #1324811) | Cod sursa (job #69532) | Cod sursa (job #2116849)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
void Dfs1 (int cur_node, vector < vector < int > > &gr,
vector < bool > &used, stack < int > &stk) {
used[cur_node] = true;
for (int x : gr[cur_node]) {
if (used[x]) {
continue;
}
Dfs1 (x, gr, used, stk);
}
stk.push (cur_node);
}
void Dfs2 (int cur_node, vector < vector < int > > &gr,
vector < bool > &used, vector < vector < int > > &sol, int &cnt) {
used[cur_node] = true;
sol[cnt].push_back (cur_node);
for (int x : gr[cur_node]) {
if (used[x]) {
continue;
}
Dfs2 (x, gr, used, sol, cnt);
}
}
int main () {
int n, m;
cin >> n >> m;
vector < vector < int > > gr (n + 1), rev (n + 1);
for (int i = 1; i <= m; ++ i) {
int x, y;
cin >> x >> y;
gr[x].push_back (y);
rev[y].push_back (x);
}
vector < bool > used (n + 1);
stack < int > stk;
for (int i = 1; i <= n; ++ i) {
if (used[i]) {
continue;
}
Dfs1 (i, gr, used, stk);
}
for (auto &&x : used) {
x = false;
}
int cnt = 0;
vector < vector < int > > sol (n + 1);
while (not stk.empty ()) {
int cur = stk.top ();
stk.pop ();
if (not used[cur]) {
++ cnt;
Dfs2 (cur, rev, used, sol, cnt);
}
}
cout << cnt << '\n';
for (int i = 1; i <= cnt; ++ i) {
for (int x : sol[i]) {
cout << x << ' ';
}
cout << '\n';
}
}