Cod sursa(job #3216134)

Utilizator NathanBBerintan Emanuel Natanael NathanB Data 15 martie 2024 17:42:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <bits/stdc++.h>

using namespace std;

const int Lim = 1e6;
int p = Lim-1;
char buf[Lim];
void next()
{
  if(p==Lim)
    {fread(buf,1,Lim,stdin);
     p = 0;}
  else p++;
}

void get(int &x)
{
  while(!isdigit(buf[p]))next();
  x = 0;
  for(;isdigit(buf[p]);next())
  {
    x*=10;
    x += buf[p] - '0';
  }
}
#define eb emplace_back
#define pb push_back
#define Inf 0x3f3f3f3f
using vi = vector<int>;
using vvi = vector<vi>;

const int Nmax = 1e5+10;
vvi G;
int n,m;
int nrcomp=0;
vvi compctc;

int incomp[Nmax],disc[Nmax],low[Nmax];
stack<int> stk;
bool instk[Nmax];
int t = 0;
void dfs(int nod)
{
    t++;
    disc[nod] = t;
    low[nod] = t;
    stk.push(nod);
    instk[nod] = true;
    for(auto c:G[nod])
    {
      //cout<<"merg: "<<nod<<" "<<c<<endl;
      if(disc[c]==Inf)
      {
        dfs(c);
        low[nod] = min(low[nod],low[c]);
      }
      else if(instk[c]) low[nod] = min(low[nod],disc[c]);
    }
    if(low[nod]==disc[nod])
    {
      nrcomp++;
      vi aux;
      compctc.pb(aux);
      int now=-1;
      while(now!=nod&&stk.size()>0)
      {
        now = stk.top();
        incomp[now] = nrcomp;
        compctc[nrcomp].eb(now);
        instk[now] = false;
        stk.pop();
      }
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    get(n);
    get(m);
    G = vvi(n+1);
    vi aux;
    compctc.pb(aux);
    for(int i=1;i<=n;i++)
      disc[i] = low[i] = Inf;
    for(int i=1;i<=m;i++)
    {
      int x,y;
      get(x);
      get(y);
      G[x].eb(y);
    }
    for(int i=1;i<=n;i++)
      if(disc[i]==Inf)
      {
      t = 0;
      dfs(i);
      }
    printf("%d\n",nrcomp);
    for(int i=1;i<=nrcomp;i++)
    {for(auto c:compctc[i])
      printf("%d ",c);
     printf("\n");
    }
    return 0;
}