Pagini recente » Cod sursa (job #260746) | Cod sursa (job #205069) | Cod sursa (job #824569) | Cod sursa (job #2950514) | Cod sursa (job #1208445)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 100005;
vector<int> G[MAXN], actual_comp;
vector< vector<int> > Components;
stack<int> S;
bool in_stack[MAXN];
int N, M, ind, index[MAXN], lowlink[MAXN];
void Read() {
fin >> N >> M;
int a, b;
for (int i = 0; i < M; ++i) {
fin >> a >> b;
G[a].push_back(b);
}
}
void tarjan(int node) {
index[node] = lowlink[node] = ind++;
S.push(node);
in_stack[node] = true;
vector<int>::iterator it;
for (it = G[node].begin(); it != G[node].end(); ++it) {
if (index[*it] == -1) {
tarjan(*it);
lowlink[node] = min(lowlink[node], lowlink[*it]);
}else if (in_stack[*it]) {
lowlink[node] = min(lowlink[node], lowlink[*it]);
}
}
if (index[node] == lowlink[node]) {//we've found a stongly connected component
actual_comp.clear();
int aux;
do {
aux = S.top();
actual_comp.push_back(aux);
S.pop();
in_stack[node] = 0;
}while (node != aux);
Components.push_back(actual_comp);
}
}
void Solve() {
memset(index, -1, sizeof(index));
for (int i = 1; i <= N; ++i) {
if (index[i] == -1)
tarjan(i);
}
}
void Write() {
fout << Components.size() << "\n";
for (size_t i = 0; i < Components.size(); ++ i) {
for (size_t j = 0; j < Components[i].size(); ++ j)
fout << Components[i][j] << " ";
fout << "\n";
}
}
int main() {
Read();
Solve();
Write();
fin.close();
fout.close();
return 0;
}