Pagini recente » Cod sursa (job #2196988) | Cod sursa (job #1214941) | Cod sursa (job #3169042) | Statistici nespecificat (Snavenport) | Cod sursa (job #2190643)
#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 = 3e6 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;
void dfs(int node,int& nrComp, vector<bool>& inStack,
stack<int>& st, vector< vector<int> >& adj, vector< vector<int> >& comp, vector<int>& index, vector<int>& lowlink) {
static int idx = 0;
++idx;
index[node] = lowlink[node] = idx;
inStack[node] = true;
st.push(node);
for (int nxt : adj[node]) {
if (index[nxt] == 0) {
dfs(nxt, nrComp, inStack, st, adj, comp, index, lowlink);
lowlink[node] = min(lowlink[node], lowlink[nxt]);
}
else if (inStack[nxt] != 0) {
lowlink[node] = min(lowlink[node], index[nxt]);
}
}
if (index[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() {
int N,M,nrComp = 0;
in >> N >> M;
vector< vector<int> > adj(N+1), comp(N+1);
vector< int > index(N+1,0),lowlink(N+1,0);
vector< bool > inStack(N+1, false);
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 (index[i]) {
continue;
}
stack<int> st;
dfs(i, nrComp, inStack, st, adj, comp, index, lowlink);
}
out << nrComp << '\n';
for (int i = 1;i <= nrComp;++i) {
for (int node : comp[i]) {
out << node << ' ';
}
out << '\n';
}
return 0;
}