Cod sursa(job #2927047)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 19 octombrie 2022 11:09:50
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#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;
}