Pagini recente » Cod sursa (job #2859506) | Cod sursa (job #1931455) | Cod sursa (job #1636466) | Cod sursa (job #2548135) | Cod sursa (job #2338031)
// By Stefan Radu
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define sz(x) (int)(x).size()
typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
stack < int > stk;
void Dfs1(int curNode, vector < vector < int > > &gr, vector < bool > &used) {
used[curNode] = true;
for (auto x : gr[curNode]) {
if (used[x]) continue;
Dfs1(x, gr, used);
stk.push(x);
}
}
vector < int > aux;
void Dfs2(int curNode, vector < vector < int > > &gr, vector < bool > &used) {
used[curNode] = true;
aux.push_back(curNode);
for (auto x : gr[curNode]) {
if (used[x]) continue;
Dfs2(x, gr, used);
}
}
int main() {
int n, m;
cin >> n >> m;
vector < vector < int > > gr (n + 1), invGr (n + 1);
for (int i = 1; i <= m; ++ i) {
int a, b;
cin >> a >> b;
gr[a].push_back (b);
invGr[b].push_back (a);
}
vector < bool > used(n + 1);
Dfs1(1, gr, used);
fill(used.begin(), used.end(), false);
vector < vector < int > > sol;
while (not stk.empty()) {
int cur = stk.top();
stk.pop();
if (used[cur]) continue;
Dfs2(cur, invGr, used);
sol.push_back(aux);
aux.clear();
}
cout << sz(sol) << '\n';
for (auto vect : sol) {
for (auto x : vect) cout << x << ' ';
cout << '\n';
}
}