Cod sursa(job #2925943)

Utilizator razvan1403razvan razvan1403 Data 16 octombrie 2022 14:13:24
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 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;

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

void dfs_stack(int node, vector<int> adj[]){
  viz[node] = 1;
  for(int i=0;i<adj[node].size();i++){
    if(viz[adj[node][i]] == 0)
      dfs_stack(adj[node][i], adj);
  }
  st.push(node);
}

void dfs_final(int node, vector<int> transpose[], int componenta){
  viz[node] = componenta;
  for(int i=0;i<transpose[node].size();i++){
    if(viz[transpose[node][i]] == 0)
      dfs_final(transpose[node][i], transpose, componenta);
  }
}


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];
  vector<int> transpose[n+1];
  long x,y;
  for(int i=0;i<m;i++)
  {
    fin>>x>>y;
    add(x,y,adj);
    add(y,x,transpose);
  }
  viz = vector<int> (n+1, 0);
  int numar_componente = 0;

  for(int i=1;i<=n;i++){
    if(viz[i] == 0)
      dfs_stack(i, adj);
  }

  viz = vector<int> (n+1, 0);

  while(!st.empty()){
    int x = st.top();
    st.pop();
    if(viz[x] == 0){
      numar_componente += 1;
      dfs_final(x, transpose, numar_componente);
    }
  }
  fout<<numar_componente<<"\n";
  for(int i=1;i<=numar_componente;i++){
    for(int j=1;j<=n;j++)
      if(viz[j] == i)
        fout<<j<<" ";
    fout<<"\n";
  }
  fin.close();
  fout.close();
}