Cod sursa(job #2924694)

Utilizator razvan1403razvan razvan1403 Data 8 octombrie 2022 18:26:17
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

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

void dfs_plus(int node, vector<int>&viz_plus, vector<int> adj[]){
  viz_plus[node] = 1;
  for(int i=0;i<adj[node].size();i++){
    if(viz_plus[adj[node][i]] == 0)
      dfs_plus(adj[node][i], viz_plus, adj);
  }
}

void dfs_minus(int node, vector<int>&viz_minus, vector<int> adj[]){
  viz_minus[node] = 1;
  for(int i=0;i<adj[node].size();i++){
    if(viz_minus[adj[node][i]] == 0)
      dfs_minus(adj[node][i], viz_minus, adj);
  }
}

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);
  }
  vector<int> viz_plus(n+1, 0);
  vector<int> viz_minus(n+1, 0);
  vector<int> componenta(n+1, 0);
  int numar_componente = 0;

  for(int i=1;i<=n;i++){
    if(componenta[i] == 0)
    {
      for(int j=1;j<=n;j++){
        viz_plus[j] = 0;
        viz_minus[j] = 0;
      }

      numar_componente+=1;
      dfs_plus(i, viz_plus, adj);
      dfs_minus(i, viz_minus, transpose);
      for(int j=1;j<=n;j++){
        if(viz_plus[j] == 1 && viz_minus[j] == 1){
          componenta[j] = numar_componente;
        }
      }
    }
  }

  fout<<numar_componente<<endl;
  for(int i=1;i<=numar_componente;i++)
  {
    for(int j=1;j<=n;j++)
    {
      if(componenta[j] == i){
        fout<<j<<" ";
      }
    }
    fout<<endl;
  }
  fin.close();
  fout.close();
}