Pagini recente » Statistici Moldoveanu Alexandru (Moldo97) | Cod sursa (job #2783442) | Cod sursa (job #1005220) | Statistici capalnean Sorana (Sorana) | Cod sursa (job #2854967)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100005
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, comp_cur;
bool viz[NMAX];
vector<int> G[NMAX], GT[NMAX], CTC[NMAX];
stack<int> st;
void citire() {
f >> n >> m;
int x, y;
for (int i = 1; i <= m; ++i) {
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void dfs_graf(int x) {
viz[x] = true;
for (auto &nod: G[x])
if (!viz[nod])
dfs_graf(nod);
st.push(x);
}
void resetare_viz() {
for (int i = 1; i <= n; ++i)
viz[i] = false;
}
void dfs_graf_transpus(int x) {
CTC[comp_cur].push_back(x);
viz[x]=true;
for (auto &nod: GT[x])
if (!viz[nod])
dfs_graf_transpus(nod);
}
void Kosaraju() {
//Parcurgere graf
for (int i = 1; i <= n; ++i)
if (!viz[i])
dfs_graf(i);
resetare_viz();
//Parcurgere graf transpus
while (!st.empty()) {
int nod = st.top();
st.pop();
if (viz[nod])
continue;
comp_cur++;
dfs_graf_transpus(nod);
}
}
void afisare() {
g << comp_cur << '\n';
for (int i = 1; i <= comp_cur; ++i) {
for (auto &nod: CTC[i])
g << nod << ' ';
g << '\n';
}
}
int main() {
citire();
Kosaraju();
afisare();
}