Cod sursa(job #2077747)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 28 noiembrie 2017 16:00:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
#define MIN(a ,b) ((a < b) ? a : b)
int const nmax = 100000;
vector<int> g[5 + nmax];
vector<int> sol[5 + nmax];
vector<int> comp;
int solp = 0;
int idx[5 + nmax] ,lowlink[5 + nmax];
int in_stack[5 + nmax];
int indecs = 0;

void dfs(int node){
  idx[node] = lowlink[node] = indecs;
  indecs++;
  in_stack[node] = 1;
  comp.push_back(node);
  for(int i = 0 ; i < g[node].size() ;i++){
    int newnode = g[node][i];
    if(idx[newnode] == -1){
      dfs(newnode);
      lowlink[node] = MIN(lowlink[node] ,lowlink[newnode]);
      ///daca e mai mare nu ne intereseaza
      ///dar daca e mai mic =>
      ///var 1 = e de la alta componenta conexa
      ///var 2 = e din componenta noastra
      ///dar nu poate fi din alta componenta conexa deoarece nodurile care sunt considerate
      ///vor fi ori din stack(adica componenta noastra) ori nevizitate
      ///e din componenta noastra
    } else if(in_stack[newnode] == 1){///e din componenta noastra conexa
      lowlink[node] = MIN(lowlink[node] ,lowlink[newnode]);
    }
  }
  if(idx[node] == lowlink[node]){///e node radacina?
    int newnode;
    do{
      newnode = comp.back();
      sol[solp].push_back(newnode);
      in_stack[newnode] = 0;
      comp.pop_back();
    } while(0 < comp.size() && newnode != node);
    solp++;
  }
}
int main()
{
  int n , m;
  in>>n>>m;
  for(int i = 1 ; i <= m ;i++){
    int x , y;
    in>>x>>y;
    g[x].push_back(y);
  }
  for(int i = 1 ; i <= n ;i++)
    idx[i] = -1;
  for(int i = 1 ; i <= n ;i++){
    if(idx[i] == -1){
      dfs(i);
    }
  }
  out<<solp<<'\n';
  for(int i = 0 ; i < solp ;i++){
    for(int j = 0 ; j < sol[i].size() ;j++){
      out<<sol[i][j]<<" ";
    }
    out<<'\n';
  }
  return 0;
}