Pagini recente » Cod sursa (job #1868389) | Cod sursa (job #2153919) | Cod sursa (job #314386) | Cod sursa (job #65208) | Cod sursa (job #3041013)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define NMAX 100005
int n, m, nrctc;
vector<int> G[NMAX], GT[NMAX];
vector<int> comp[NMAX];
bitset<NMAX> viz;
stack<int> st;
void citire() {
f >> n >> m;
int x, y;
for (int i = 0; i < m; ++i) {
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void dfs(int x) {
viz.set(x);
for (auto &nod: G[x])
if (!viz[nod])
dfs(nod);
st.push(x);
}
void dfs_transpus(int x) {
viz.set(x);
comp[nrctc].push_back(x);
for (auto &nod: GT[x])
if (!viz[nod])
dfs_transpus(nod);
}
void componente_tare_conexe() {
//parcurgere graf
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
viz.reset();
//parcurgere graf transpus
while (!st.empty()) {
int x = st.top();
st.pop();
if (viz[x])
continue;
dfs_transpus(x);
nrctc++;
}
}
void afisare() {
g << nrctc << '\n';
for (int i = 0; i < nrctc; ++i) {
for (auto &nod: comp[i])
g << nod << ' ';
g << '\n';
}
}
int main() {
citire();
componente_tare_conexe();
afisare();
return 0;
}