Cod sursa(job #3214283)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 14 martie 2024 00:22:56
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAXN 100

using namespace std;

vector<vector<int>> v, vt; // vt = v transpus
stack<int> nodes;
bool visited[MAXN];

vector<vector<int>> r;

FILE *fin, *fout;
int n,m;

void dfs(int id){
  visited[id] = true;
  for(int i = 0; i < v[id].size(); i ++ )
    if(!visited[v[id][i]])
      dfs(v[id][i]);

  nodes.push(id);
}
void double_dfs(int id, int start){
  visited[id] = true;
  r[start].push_back(id);

  for(int i = 0; i < vt[id].size(); i ++ )
    if(!visited[vt[id][i]])
      double_dfs(vt[id][i], start);
}

void kosaraju(){
  while(nodes.size())
    nodes.pop();
  for(int i = 0; i < n; i ++)
    visited[i] = false;
  for(int i = 0; i < n; i ++)
    if(!visited[i])
      dfs(i);

  for(int i = 0; i < n; i ++)
    visited[i] = false;
  while(!nodes.empty()){
    int node = nodes.top();
    nodes.pop();

    if(!visited[node])
      double_dfs(node, node);
  }

  int nr = 0;
  for(int i = 0; i < n; i ++){
    if(r[i].size() > 0)
      nr ++;
  }
  fprintf(fout, "%d\n", nr);
  for(int i = 0; i < n; i ++){
    if(r[i].size() > 0){
      sort(r[i].begin(), r[i].end());

      for(int j = 0; j < r[i].size(); j ++)
        fprintf(fout, "%d ", r[i][j] + 1);
      fprintf(fout, "\n");
    }
  }
}

void tarjan(){
  // Not Implemented
}


int main(){
  fin = fopen("ctc.in" ,"r");
  fscanf(fin, "%d%d", &n, &m);
  v.resize(n);
  vt.resize(n);
  r.resize(n);

  for(int i = 0; i < m; i ++){
    int a, b;
    fscanf(fin, "%d%d", &a, &b);
    v[a - 1].push_back(b - 1);
    vt[b - 1].push_back(a - 1);
  }
  fclose(fin);

  fout = fopen("ctc.out", "w");
  kosaraju();
  fclose(fout);
  return 0;
}