Pagini recente » Cod sursa (job #1172791) | Cod sursa (job #2751274) | Cod sursa (job #1703898) | Cod sursa (job #263818) | Cod sursa (job #2976957)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T, size_t N>
void re(array <T, N>& x);
template <class T>
void re(vt <T>& x);
template <class T>
void re(T& x) {
cin >> x;
}
template <class T, class... M>
void re(T& x, M&... args) {
re(x); re(args...);
}
template <class T>
void re(vt <T>& x) {
for(auto& it : x)
re(it);
}
template <class T, size_t N>
void re(array <T, N>& x) {
for(auto& it : x)
re(it);
}
template <class T, size_t N>
void wr(array <T, N> x);
template <class T>
void wr(vt <T> x);
template <class T>
void wr(T x) {
cout << x;
}
template <class T, class ...M> void wr(T x, M... args) {
wr(x), wr(args...);
}
template <class T>
void wr(vt <T> x) {
for(auto it : x)
wr(it, ' ');
}
template <class T, size_t N>
void wr(array <T, N> x) {
for(auto it : x)
wr(it, ' ');
}
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
void solve() {
/* Tarjan's algorithm */
function <void(int)> dfs;
int n, m; re(n, m);
vt <vt <int>> adj(n), res;
vt <int> low_link(n), index(n);
vt <bool> on_stack(n);
stack <int> st;
for (int i = 0; i < m; ++i) {
int u, v; re(u, v);
--u, --v;
adj[u].emb(v);
}
/* Low-Link Value
The low-link value of a node is the smallest [lowest] node
id reachable from that node when doing a DFS (including itself)
All Strongly Connected Components have their low-link value the same.
*/
int idx = 0;
dfs = [&](int u) {
index[u] = ++idx;
low_link[u] = index[u];
st.push(u);
on_stack[u] = true;
for (int v : adj[u]) {
if (index[v] == 0) {
// update the low-link value
dfs(v);
low_link[u] = min(low_link[u], low_link[v]);
} else if (on_stack[v]) {
//update the low-link value
low_link[u] = min(low_link[u], low_link[v]);
}
}
/* when we have the same low-link value as the index
we know that here lies the start of a Strongly Connected Component
and we empty the stack.
*/
if (low_link[u] == index[u]) {
vt <int> tmp;
int top;
do {
top = st.top();
tmp.emb(top + 1);
on_stack[top] = false;
st.pop();
} while(top != u);
res.emb(tmp);
}
};
for (int u = 0; u < n; ++u)
if (index[u] == 0) {
dfs(u);
}
wr(len(res), '\n');
for (int i = 0; i < len(res); ++i)
wr(res[i], '\n');
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Open("ctc");
int t = 1;
for(;t;t--) {
solve();
}
return 0;
}