Cod sursa(job #2502793)

Utilizator ValentinStStamate Valentin ValentinSt Data 1 decembrie 2019 16:45:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int n, m;
bool viz[100001], showTime;
vector<int> G[100001];
vector<int> GT[100001];

int nr;
vector<int> SCC[100001];

stack<int> s;

void DFSTareConex(int i);
void GetT();
void ShowSCC();
void DFS(int i);
void printG();

int main(){
  
  in>>n>>m;
  for(int l = 0; l < m; l++){
    int i, j;
    in>>i>>j;
    G[i].push_back(j);
  }
  for(int i = 1; i <= n; i++){
    viz[i] = false;
  }

  for(int i = 1; i <= n; i++){
    if(viz[i] == false)
      DFSTareConex(i);
  }

  GetT();

  ShowSCC();

  //printG();
  return 0;
}

void printG(){

  for(int i = 1; i <= n; i++){
    out<<i<<" ";
    for(int j = 0; j < GT[i].size(); j++){
      out<<G[i].at(j)<<" ";
    }
    out<<"\n";
  }

}

void DFSTareConex(int i){
  viz[i] = true;

  for(int l = 0; l < G[i].size(); l++){
    int n = G[i].at(l);
    if(viz[n] == false){
      DFSTareConex(n);
    }
  }

  s.push(i);
}

void GetT(){

  for(int i = 1; i <= n; i++){
    for(int j = 0; j < G[i].size(); j++){
      int n = G[i].at(j);
      GT[n].push_back(i);
    }
  }

}

void ShowSCC(){

  for(int i = 1; i <= n; i++){
    viz[i] = false;
  }

  while(!s.empty()){
    int i = s.top();
    s.pop();
    if(viz[i] == false){
      nr++;
      DFS(i);
    }

  }

  out<<nr<<"\n";
  for(int i = 1; i <= nr; i++){
    for(int j = 0; j < SCC[i].size(); j++){
      out<<SCC[i].at(j)<<" ";
    }
    out<<"\n";
  }


}

void DFS(int i){
  viz[i] = true;
  SCC[nr].push_back(i);
  
  for(int j = 0; j < GT[i].size(); j++){
    int n = GT[i].at(j);
    if(viz[n] == false){
      DFS(n);
    }
  }

}