Pagini recente » Cod sursa (job #186348) | Cod sursa (job #2374513) | Cod sursa (job #2781349) | Cod sursa (job #2792071) | Cod sursa (job #2927047)
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 100000
int noduri[MAXN], aux[MAXN], ord[MAXN];
vector <int> graf[MAXN];
vector <int> invgraf[MAXN];
vector <int> comp[MAXN];
void dfsstart(int nod, int &ind){
int i;
noduri[nod] = 1;
for(i = 0; i < graf[nod].size(); i++){
if(noduri[graf[nod][i]] == 0){
dfsstart(graf[nod][i], ind);
}
}
ord[ind] = nod;
ind++;
}
void dfsdirect(int nod, int &ind){
int i;
noduri[nod] = 1;
aux[ind] = nod;
ind++;
for(i = 0; i < graf[nod].size(); i++){
if(noduri[graf[nod][i]] == 0){
dfsdirect(graf[nod][i], ind);
}
}
}
void dfsinv(int nod, int &nrc){
int i;
noduri[nod] = 2;
comp[nrc].push_back(nod);
for(i = 0; i < invgraf[nod].size(); i++){
if(noduri[invgraf[nod][i]] == 1){
dfsinv(invgraf[nod][i], nrc);
}
}
}
int findcomponente(int n){
int i, ind, j, nrc;
for(i = 0; i < n; i++){
noduri[i] = 0;
}
nrc = 0;
for(i = 0; i < n; i++){
if(noduri[i] == 0){
ind = 0;
dfsdirect(i, ind);
dfsinv(i, nrc);
for(j = 0; j < ind; j++){
if(noduri[aux[j]] == 1){
noduri[aux[j]] = 0;
}
}
nrc++;
}
}
return nrc;
}
int main()
{
FILE *fin, *fout;
int n, m, i, a, b, ind, nrc, j;
fin = fopen("ctc.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(i = 0; i < m; i++){
fscanf(fin, "%d%d", &a, &b);
graf[a - 1].push_back(b - 1);
invgraf[b - 1].push_back(a - 1);
}
fclose(fin);
ind = 0;
for(i = 0; i < n; i++){
if(noduri[i] == 0){
dfsstart(i, ind);
}
}
nrc = findcomponente(n);
fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", nrc);
for(i = 0; i < nrc; i++){
for(j = 0; j < comp[i].size(); j++){
fprintf(fout, "%d ", comp[i][j] + 1);
}
fprintf(fout, "\n");
}
fclose(fout);
return 0;
}