Pagini recente » Cod sursa (job #1386289) | Cod sursa (job #880254) | Cod sursa (job #304123) | Cod sursa (job #2434637) | Cod sursa (job #1208490)
#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;
stack<int> S;
vector<int> G[MAXN], actual_component;
vector< vector<int> > Components;
int ind = 0, indx[MAXN], N, M, level[MAXN];
bool in_stack[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 father) {
indx[father] = level[father] = ind++;
S.push(father); in_stack[father] = true;
vector<int>::iterator it;
for (it = G[father].begin(); it != G[father].end(); ++it) {
if (indx[*it] == -1) {
Tarjan(*it);
level[father] = min(level[father], level[*it]);
}else if (in_stack[*it]) {
level[father] = min(level[father], level[*it]);
}
}
if (indx[father] == level[father]) {
actual_component.clear();
int naux;
do {
naux = S.top();
S.pop(); in_stack[naux] = false;
actual_component.push_back(naux);
}while (father != naux);
Components.push_back( actual_component );
}
}
void Solve() {
memset(indx, -1, sizeof(indx));
for (int i = 1; i <= N; ++i)
if (indx[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;
}