Pagini recente » Cod sursa (job #2172421) | Cod sursa (job #1777837) | Cod sursa (job #3186405) | Cod sursa (job #370855) | Cod sursa (job #1947804)
/**
* Worg
*/
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
using std::stack;
using std::vector;
FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);
const int kMaxN = 1 + 100000;
/*-------- Input data --------*/
int N, M;
vector<int > graph[kMaxN];
/*-------- SCC data --------*/
stack<int > my_stack;
bool in_stack[kMaxN];
int index[kMaxN], lowlink[kMaxN];
int crt_index;
vector<int > scc;
vector<vector<int > > scc_list;
/*-------- --------*/
void ReadInput() {
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++) {
int x, y; scanf("%d%d", &x, &y);
graph[x].push_back(y);
}
}
void DFS(int node) {
crt_index ++;
index[node] = lowlink[node] = crt_index;
my_stack.push(node); in_stack[node] = true;
for(int nxt : graph[node]) {
if(!index[nxt]) {
DFS(nxt);
lowlink[node] = std::min(lowlink[node], lowlink[nxt]);
} else if(in_stack[nxt]) {
lowlink[node] = std::min(lowlink[node], index[nxt]);
}
}
if(lowlink[node] == index[node]) {
scc.clear();
int now;
do {
now = my_stack.top(); my_stack.pop();
scc.push_back(now); in_stack[now] = false;
}while(now != node);
scc_list.push_back(scc);
}
}
void TarjanAlgo() {
crt_index = 0;
for(int i = 1; i <= N; i++) {
if(!index[i]) {
DFS(i);
}
}
}
void WriteOutput() {
printf("%d\n", (int)scc_list.size());
for(auto comp : scc_list) {
for(auto node : comp) {
printf("%d ", node);
}
printf("\n");
}
}
int main() {
ReadInput();
TarjanAlgo();
WriteOutput();
return 0;
}