Pagini recente » Cod sursa (job #2238091) | Cod sursa (job #1980882) | Cod sursa (job #2258033) | Cod sursa (job #1480517) | Cod sursa (job #2190646)
#include <bits/stdc++.h>
using namespace std;
#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif
#ifdef ONLINE_JUDGE
#define in cin
#define out cout
#else
ifstream in("ctc.in");
ofstream out("ctc.out");
#endif
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 1e5 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;
int N,M,nrComp;
vector<bool> inStack(NMax , false);
vector<int> idx(NMax, 0),lowlink(NMax), comp[NMax], adj[NMax];
stack<int> st;
void dfs(int node) {
static int counter = 0;
++counter;
idx[node] = lowlink[node] = counter;
inStack[node] = true;
st.push(node);
for (int nxt : adj[node]) {
if (!idx[nxt]) {
dfs(nxt);
lowlink[node] = min(lowlink[node], lowlink[nxt]);
}
else if (inStack[nxt]) {
lowlink[node] = min(lowlink[node], lowlink[nxt]);
}
}
if (idx[node] == lowlink[node]) {
++nrComp;
int curr = 0;
do {
curr = st.top();
st.pop();
comp[nrComp].pb(curr);
inStack[curr] = false;
} while (curr != node);
}
}
int main() {
in >> N >> M;
for (int i = 1;i <= M;++i) {
int x,y;
in >> x >> y;
adj[x].pb(y);
}
for (int i = 1;i <= N;++i) {
if (idx[i]) {
continue;
}
dfs(i);
}
out << nrComp << '\n';
for (int i = 1;i <= nrComp;++i) {
for (int node : comp[i]) {
out << node << ' ';
}
out << '\n';
}
return 0;
}