Pagini recente » Diferente pentru implica-te/imbunatatire-teste intre reviziile 13 si 12 | Statistici Nedelcu Stefan Daniel (Archerraiko) | Cod sursa (job #3282308) | Monitorul de evaluare | Cod sursa (job #1899058)
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> *G, *Gt, *C;
bool *viz, *A;
int *L, sp;
void dfs(int u)
{
if (!viz[u]) {
viz[u] = true;
for (unsigned int i = 0; i < G[u].size(); ++i) {
dfs(G[u][i]);
}
L[++sp] = u;
}
}
void assign(int u, int root)
{
if (!A[u]) {
A[u] = 1;
C[root].push_back(u);
for (unsigned int i = 0; i < Gt[u].size(); ++i) {
assign(Gt[u][i], root);
}
}
}
int main()
{
FILE *fin, *fout;
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
int N, M;
fscanf(fin, "%d%d", &N, &M);
G = new vector<int>[N+1]();
Gt = new vector<int>[N+1]();
for (int i = 0; i < M; ++i) {
int x, y;
fscanf(fin, "%d%d", &x, &y);
G[x].push_back(y);
Gt[y].push_back(x);
}
L = new int[N+1]();
A = new bool[N+1]();
viz = new bool[N+1]();
C = new vector<int>[N+1]();
for (int i = 1; i <= N; ++i) {
dfs(i);
}
for (int i = N; i >= 1; --i) {
assign(L[i], L[i]);
}
int nc = 0;
for (int i = 1; i <= N; ++i) {
if (C[i].size()) {
++nc;
}
}
fprintf(fout, "%d\n", nc);
for (int i = 1; i <= N; ++i) {
if (C[i].size()) {
for (unsigned int u = 0; u < C[i].size(); ++u) {
fprintf(fout, "%d ", C[i][u]);
}
fprintf(fout, "\n");
}
}
fclose(fin);
fclose(fout);
return 0;
}