Pagini recente » Cod sursa (job #636027) | Cod sursa (job #1892477) | Cod sursa (job #2254675) | Cod sursa (job #3222197) | Cod sursa (job #662013)
Cod sursa(job #662013)
#include <stdio.h>
#include <vector>
#define DIM 100010
using namespace std;
struct nod {
int inf;
nod *adr;
};
int minim(int a, int b) {
return a<b ? a : b;
}
int inStack[DIM];
vector<int> L[DIM];
nod *V[DIM], *q;
int N, M, i, j, X, Y, comp, s, niv;
int Niv[DIM], Min[DIM], S[DIM];
void tarjan(int x) {
niv ++;
Niv[x] = Min[x] = niv;
S[++s] = x;
inStack[x] = 1;
for (nod *q = V[x]; q != NULL; q = q->adr) {
if (Niv[q->inf] == 0) {
tarjan(q->inf);
Min[x] = minim(Min[x], Min[q->inf]);
} else
if (inStack[q->inf])
Min[x] = minim(Min[x], Min[q->inf]);
}
if (Min[x] == Niv[x]) {
comp++;
do {
L[comp].push_back(S[s--]);
inStack[S[s+1]] = 0;
} while (S[s+1]!=x);
}
}
int main() {
FILE *f = fopen("ctc.in", "r");
FILE *g = fopen("ctc.out", "w");
fscanf(f,"%d %d", &N, &M);
for (i=1;i<=M;i++) {
fscanf(f,"%d %d",&X, &Y);
q = new nod;
q->inf = Y;
q->adr = V[X];
V[X] = q;
}
fclose(f);
for (i=1;i<=N;i++)
if (Niv[i] == 0)
tarjan(i);
fprintf(g,"%d\n",comp);
for (i=1;i<=comp;i++) {
for (j=0;j<L[i].size();j++)
fprintf(g,"%d ",L[i][j]);
fprintf(g,"\n");
}
return 0;
}