Pagini recente » Cod sursa (job #234808) | Cod sursa (job #1151254) | Cod sursa (job #736728) | Cod sursa (job #3290569) | Cod sursa (job #1208448)
#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, indexx[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) {
indexx[node] = lowlink[node] = ind; ++ind;
S.push(node);
in_stack[node] = true;
vector<int>::iterator it;
for (it = G[node].begin(); it != G[node].end(); ++it) {
if (indexx[*it] == -1) {
tarjan(*it);
lowlink[node] = min(lowlink[node], lowlink[*it]);
}else if (in_stack[*it]) {
lowlink[node] = min(lowlink[node], lowlink[*it]);
}
}
if (indexx[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] = false;
}while (node != aux);
Components.push_back(actual_comp);
}
}
void Solve() {
for (int i = 1; i <= N; ++i)
indexx[i] = -1;
for (int i = 1; i <= N; ++i) {
if (indexx[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;
}