Pagini recente » Cod sursa (job #804354) | Cod sursa (job #3199757) | Cod sursa (job #1232184) | Cod sursa (job #762380) | Cod sursa (job #1977034)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100002
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> graf[NMAX];
vector<int> SCC[NMAX];
int ind[NMAX], lowlink[NMAX];
bitset<NMAX> inStack;
stack<int> stiva;
int nrSCC = 0;
void getSCC(int node) {
int x;
do {
x = stiva.top();
stiva.pop();
inStack[x] = 0;
SCC[nrSCC].push_back(x);
}while(x != node);
nrSCC++;
}
int idx = 0;
void DFS(int node) {
lowlink[node] = ind[node] = ++idx;
stiva.push(node);
inStack[node] = 1;
for (auto& adj: graf[node]) {
if (!ind[adj]) {
DFS(adj);
lowlink[node] = min(lowlink[node], lowlink[adj]);
}
else
lowlink[node] = min(lowlink[node], ind[adj]);
}
if (lowlink[node] == ind[node])
getSCC(node);
}
int main() {
int N, M;
fin >> N >> M;
int x, y;
while (M--) {
fin >> x >> y;
graf[x].push_back(y);
}
for (int i = 1; i <= N; ++i) {
if (!ind[i])
DFS(i);
}
fout << nrSCC << "\n";
for (int i = 0; i < nrSCC; ++i) {
for (auto& node: SCC[i])
fout << node << " ";
fout << "\n";
}
return 0;
}