Pagini recente » Cod sursa (job #420016) | Cod sursa (job #1583211) | Cod sursa (job #608867) | Cod sursa (job #3004090) | Cod sursa (job #2338037)
// 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(curNode);
}
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() {
/* ios::sync_with_stdio(false); */
/* cin.tie(0);cout.tie(0); */
/* freopen("input", "r", stdin); */
/* freopen("output", "w", stdout); */
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);
for (int i = 1; i <= n; ++ i) {
if (used[i]) continue;
Dfs1(i, 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';
}
}