Pagini recente » Cod sursa (job #2146368) | Monitorul de evaluare | Cod sursa (job #1239688) | Cod sursa (job #1287721) | Cod sursa (job #1132557)
#include <vector>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define NMAX 100001
struct nod {
int U;
nod *next;
};
nod *v[NMAX];
nod *T[NMAX];
int i, j, N, M;
int nrComp;
int A, B;
vector <int> Sorted;
vector <int> Comp[NMAX];
void add(int A, int B, nod *v[]) {
nod *P = new nod;
P->U = B;
P->next = v[A];
v[A] = P;
}
bool used[NMAX];
void TSort(int node) {
used[node] = true;
for (nod *it = v[node]; it; it = it->next) {
if (!used[it->U])
TSort(it->U);
}
Sorted.push_back(node);
}
void Kosaraju(int node) {
used[node] = true;
Comp[nrComp].push_back(node);
for (nod *it = T[node]; it; it = it->next) {
if (!used[it->U])
Kosaraju(it->U);
}
}
int main() {
fin >> N >> M;
for (i = 1; i <= M; ++i) {
fin >> A >> B;
add(A, B, v);
add(B, A, T);
}
for (i = 1; i <= N; ++i)
if (!used[i])
TSort(i);
memset(used, 0, sizeof(used));
vector <int> :: reverse_iterator it;
for (it = Sorted.rbegin(); it != Sorted.rend(); ++it) {
if (!used[*it]) {
++nrComp;
Kosaraju(*it);
}
}
fout << nrComp << '\n';
vector <int> :: iterator It;
for (i = 1; i <= nrComp; ++i) {
for (It = Comp[i].begin(); It != Comp[i].end(); ++It)
fout << *It << ' ';
fout << '\n';
}
return 0;
}