Pagini recente » Cod sursa (job #3188170) | Cod sursa (job #1611951) | Cod sursa (job #2988376) | Cod sursa (job #822768) | Cod sursa (job #1953535)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
FILE *fin = fopen("ctc.in", "r");
FILE *fout = fopen("ctc.out", "w");
#define MAX_N 100000
#define MAX_M 200000
int n, m;
vector <int> v[MAX_N + 1];
vector <int> sol[MAX_N + 1];
vector <int> stk;
int idx[MAX_N + 1];
int freeidx = 0;
bool ostk[MAX_N + 1];
int numCTC = 0;
int tarjan(int nod) {
int minPtr = idx[nod] = ++freeidx;
stk.push_back(nod);
ostk[nod] = 1;
for(auto &son : v[nod])
if(!idx[son])
minPtr = min(minPtr, tarjan(son));
else if(ostk[son])
minPtr = min(minPtr, idx[son]);
if(idx[nod] == minPtr) {
int aux;
do {
aux = stk[stk.size() - 1];
ostk[aux] = 0;
stk.pop_back();
sol[numCTC].push_back(aux);
} while(aux != nod);
numCTC++;
}
return minPtr;
}
int main() {
int i, x, y;
fscanf(fin, "%d%d", &n, &m);
for(i = 1;i <= m;i++) {
fscanf(fin, "%d%d", &x, &y);
v[x].push_back(y);
}
for(i = 1;i <= n;i++)
if(!idx[i])
tarjan(i);
fprintf(fout, "%d\n", numCTC);
for(i = 0;i < numCTC;i++) {
for(auto &nod: sol[i])
fprintf(fout, "%d ", nod);
fputc('\n', fout);
}
fclose(fin);
fclose(fout);
return 0;
}