Pagini recente » Cod sursa (job #1615452) | Cod sursa (job #1832478) | Cod sursa (job #862522) | Cod sursa (job #3257458) | Cod sursa (job #2861219)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 1e5 + 5;
int nrSCC, cnt;
int id[MAXN], low[MAXN], inStack[MAXN];
vector<int> G[MAXN], SCC[MAXN];
stack<int> st;
inline void dfs(int node) {
id[node] = low[node] = ++cnt;
st.push(node);
inStack[node] = 1;
for(auto vecin : G[node]) {
if(id[vecin] == 0)
dfs(vecin);
if(inStack[vecin] == 1)
low[node] = min(low[node], low[vecin]);
}
if(id[node] == low[node]) {
nrSCC++;
int x;
do {
x = st.top();
SCC[nrSCC].push_back(x);
low[x] = low[node];
inStack[x] = 0;
st.pop();
} while( x != node );
}
}
int main() {
int n, m, x, y;
fin >> n >> m;
while(m--) {
fin >> x >> y;
G[x].push_back(y);
}
for(int i = 1; i <= n; i++)
if(!id[i])
dfs(i);
fout << nrSCC << '\n';
for(int i = 1; i <= nrSCC; i++) {
for(int node : SCC[i])
fout << node << ' ';
fout << '\n';
}
return 0;
}