Cod sursa(job #2925958)

Utilizator razvan1403razvan razvan1403 Data 16 octombrie 2022 14:34:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
/*
  Pentru a rezolva aceasta problema o sa folosim algoritmul Plus-Minus. Pentru fiecare nod x care nu a fost inca 
  plasat intr-o componenta tare conexa o sa facem urmatorii pasi:
  - determinam toate nodurile la care putem ajunge plecand de la nodul x, marcand aceste noduri cu "plus"
  - determinam toate nodurile din care putem ajunge in x, folosind graful transpus si le marcam cu "minus"
  - la final o sa alegem nodurile care sunt marcate atat cu "plus", cat si cu "minus" ca facand parte din aceeasi
  componenta tare conexa cu un nod x
  Complexitate O(V+E), deoarece folosim lista de adiacenta pentru a memora graful
*/

#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

stack<int> st;
vector<int> viz;
vector<int> disc_time;
vector<int> low_time;
vector<bool> inStack;

vector<vector<int>> rez;

void add(int x, int y, vector<int> adj[]){
  adj[x].push_back(y);
}

void Tarjan(int node, vector<int> adj[]){
  static int time = 0;
  disc_time[node] = low_time[node] = ++time;

  st.push(node);
  inStack[node] = true;

  for(int i=0;i<adj[node].size();i++){
    if(disc_time[adj[node][i]] == -1){
      Tarjan(adj[node][i], adj);
      low_time[node] = min(low_time[node], low_time[node[adj][i]]);
    }else if(inStack[adj[node][i]] == true){
      low_time[node] = min(low_time[node], disc_time[adj[node][i]]);
    }
  }
  vector<int> x;
  if(disc_time[node] == low_time[node]){
    while(st.top() != node){
      x.push_back(st.top());
      inStack[st.top()] = false;
      st.pop();
    }
    x.push_back(st.top());
    inStack[st.top()] = false;
    st.pop();
    sort(x.begin(), x.end());
    rez.push_back(x);
  }
}

int main(){
  ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
  long n,m;
  fin>>n>>m;
  vector<int> adj[n+1];
  long x,y;
  for(int i=0;i<m;i++)
  {
    fin>>x>>y;
    add(x,y,adj);
  }
  viz = vector<int> (n+1, 0);
  disc_time = vector<int> (n+1, -1);
  low_time = vector<int> (n+1, -1);
  inStack = vector<bool> (n+1, false);

  for(int i=1;i<=n;i++){
    if(disc_time[i] == -1){
      Tarjan(i, adj);
    }
  }

  fout<<rez.size()<<endl;
  for(int i=rez.size()-1;i>=0;i--)
  {
    for(int j=0;j<rez[i].size();j++)
    {
      fout<<rez[i][j]<<" ";
    }
    fout<<endl;
  }
  
  fin.close();
  fout.close();
}