Pagini recente » Cod sursa (job #2159236) | Cod sursa (job #719360) | Cod sursa (job #2780479) | Cod sursa (job #2698359) | Cod sursa (job #2715171)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100001;
int N, M, level[NMAX], low[NMAX], cnt, scc_cnt;
vector < int > G[NMAX];
bitset < NMAX > inStack, beenThere;
stack < int > nodes;
vector < int > scc[NMAX];
void dfs(int node) {
cnt++;
level[node] = low[node] = cnt;
inStack[node] = 1;
nodes.push(node);
beenThere[node] = 1;
for(auto& it : G[node]) {
if(level[it] == 0) { // daca nu a fost vizitat fac un dfs
dfs(it);
low[node] = min(low[node], low[it]);
} else if(inStack[it] == 1)
low[node] = min(low[node], low[it]);
}
if(level[node] == low[node]) {
int x{};
scc_cnt++;
do {
x = nodes.top();
nodes.pop();
inStack[x] = 0;
scc[scc_cnt].push_back(x);
} while(x != node);
}
}
int main() {
f >> N >> M;
for(;M--;) {
int x, y;
f >> x >> y;
G[x].push_back(y);
}
for(int i = 1;i <= N;++i)
if(!beenThere[i])
dfs(i);
g << scc_cnt << '\n';
for(int i = 1;i <= scc_cnt;++i, g << '\n')
for(auto& it : scc[i])
g << it << ' ';
return 0;
}