Pagini recente » Cod sursa (job #502406) | Cod sursa (job #1446445) | Cod sursa (job #2305871) | Cod sursa (job #1379040) | Cod sursa (job #2220070)
/**
* Worg
*/
#include <stack>
#include <cstdio>
#include <vector>
FILE *fin = freopen("ctc.in", "r", stdin); FILE *fout = freopen("ctc.out", "w", stdout);
const int MAX_N = 1e5 + 5;
/*-------- Data --------*/
int n, m;
std::vector<std::vector<int > > graph;
int cursor;
int index[MAX_N], lowlink[MAX_N], inStack[MAX_N];
std::stack<int > stk;
std::vector<std::vector<int > > sccList;
/*-------- --------*/
void ReadInput() {
scanf("%d%d", &n, &m); graph.resize(n + 1);
for(int i = 0; i < m; i++) {
int u, v; scanf("%d%d", &u, &v);
graph[u].push_back(v);
}
}
void StrongConnect(int node) {
cursor++; index[node] = lowlink[node] = cursor;
stk.push(node); inStack[node] = true;
for(auto& nxt : graph[node]) {
if(!index[nxt]) {
StrongConnect(nxt);
lowlink[node] = std::min(lowlink[node], lowlink[nxt]);
} else if(inStack[node]) {
lowlink[node] = std::min(lowlink[node], index[nxt]);
}
}
// Check if the current node is the "starting point" of a new strongly connected component
if(index[node] == lowlink[node]) {
std::vector<int > currentScc;
int aux;
do {
aux = stk.top(); stk.pop(); inStack[aux] = false;
currentScc.push_back(aux);
}while(aux != node);
sccList.push_back(currentScc);
}
}
void Tarjan() {
for(int node = 1; node <= n; node++) {
if(!index[node]) {
StrongConnect(node);
}
}
}
void WriteOutput() {
printf("%d\n", (int)sccList.size());
for(auto& scc : sccList) {
for(auto& node : scc) {
printf("%d ", node);
}
printf("\n");
}
}
int main() {
ReadInput();
Tarjan();
WriteOutput();
return 0;
}