Pagini recente » Cod sursa (job #2986906) | Cod sursa (job #1374126) | Cod sursa (job #2613134) | Cod sursa (job #2155195) | Cod sursa (job #3041317)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define NMAX 100005
#define NEVIZITAT (-1)
int n, m, idcur, nrctc;
vector<int> G[NMAX];
int low[NMAX], id[NMAX];
stack<int> st;
bool in_stack[NMAX];
vector<int> comp[NMAX];
void citire() {
f >> n >> m;
int x, y;
for (int i = 0; i < m; ++i) {
f >> x >> y;
G[x].push_back(y);
}
}
void initializare() {
for (int i = 1; i <= n; ++i)
id[i] = NEVIZITAT;
}
void dfs(int x) {
id[x] = low[x] = idcur++;
st.push(x);
in_stack[x] = true;
for (auto &nod: G[x]) {
if (id[nod] == NEVIZITAT)
dfs(nod);
if (in_stack[nod])
low[x] = min(low[x], low[nod]);
}
if (id[x] == low[x]) {
nrctc++;
int nod;
do {
nod = st.top();
st.pop();
in_stack[nod] = false;
low[nod] = x;
comp[nrctc].push_back(nod);
} while (nod != x);
}
}
void Tarjan() {
for (int i = 1; i <= n; i++)
if (id[i] == NEVIZITAT)
dfs(i);
}
void afisare() {
g << nrctc << '\n';
for (int i = 1; i <= nrctc; ++i) {
for (auto &nod: comp[i])
g << nod << ' ';
g << '\n';
}
}
int main() {
citire();
initializare();
Tarjan();
afisare();
return 0;
}