Cod sursa(job #2969986)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 23 ianuarie 2023 22:54:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
const int NMAX=100005;

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

vector <int> t[NMAX], v[NMAX], c[NMAX];
stack <int> st;
int n, m, ctc, dfs;
int ct[NMAX], df[NMAX];

void dfs1(int);
void dfs2(int);

int main()
{
  int i, a, b;
  ios_base::sync_with_stdio(false);
  fin.tie(0);
  fout.tie(0);
  fin>>n>>m;
  for(i=1; i<=m; i++)
  {
    fin>>a>>b;
    v[a].push_back(b);
    t[b].push_back(a);
  }
  //daca le-ai vizitat in acelasi prim dfs si le-ai gasit si in al doilea
  //fenta face ca sunt impreunate in aceeasi componenta tare convexa(conexa e un cuvant prea lejer)
  for(i=1; i<=n; i++)
  {
    if(ct[i]==0)
    {
      ++dfs;
      dfs1(i);
      while(!st.empty())
      {
        if(ct[st.top()]==0)
        {
          ctc++;
          dfs2(st.top());
        }
        st.pop();
      }
    }
  }
  fout<<ctc<<'\n';
  for(i=1; i<=ctc; i++)
  {
    sort(c[i].begin(), c[i].end());
    for(auto j:c[i]) fout<<j<<' ';
    fout<<'\n';
  }
  return 0;
}

void dfs1(int nod)
{
  df[nod]=dfs;
  for(auto i:v[nod])
  {
    if(df[i]==0) dfs1(i);
  }
  st.push(nod);
}

void dfs2(int nod)
{
  c[ctc].push_back(nod);
  ct[nod]=ctc;
  for(auto i:t[nod])
  {
    if(ct[i]==0 && df[i]==df[nod]) dfs2(i);
  }
}