Pagini recente » Cod sursa (job #2570220) | Cod sursa (job #1930521) | Cod sursa (job #2760599) | Cod sursa (job #1756113) | Cod sursa (job #2189280)
#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 = 5e2 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
const double eps = 1e-7;
using zint = int;
void buildStack(int node, stack<int>& st, vector<bool>& inStack, vector<int>* const adj) {
inStack[node] = true;
for (int nxt : adj[node]) {
if (inStack[nxt]) {
continue;
}
buildStack(nxt, st, inStack, adj);
}
st.push(node);
}
void buildComp(int node, const int nrComp, vector<int>& compOf, vector<int>& comp, vector<int>* const adj) {
compOf[node] = nrComp;
comp.pb(node);
for (int nxt : adj[node]) {
if (compOf[nxt]) {
continue;
}
buildComp(nxt, nrComp, compOf, comp, adj);
}
}
int main() {
int N,M;
in >> N >> M;
//M = N*(N-1)/2;
vector<bool> inStack(N+1, false);
vector<int> compOf(N+1, 0),comp[N+1], adj[N + 1], rev[N + 1];
int nrComp = 0;
for (int i = 1;i <= M;++i) {
int x,y;
in >> x >> y;
adj[x].pb(y);
rev[y].pb(x);
}
stack<int> st;
for (int i = 1;i <= N;++i) {
if (inStack[i]) {
continue;
}
buildStack(i, st, inStack, adj);
}
while (st.size()) {
int node = st.top(); st.pop();
if (compOf[node]) {
continue;
}
++nrComp;
buildComp(node, nrComp, compOf, comp[nrComp], rev);
}
out << nrComp << '\n';
for (int i = 1;i <= nrComp;++i) {
for (int node : comp[i]) {
out << node << ' ';
}
out << '\n';
}
return 0;
}