Cod sursa(job #2280229)

Utilizator LorenaMariaHantig Lorena LorenaMaria Data 10 noiembrie 2018 12:52:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,a,b,r,v[100001];
vector <int> g[100001];
vector <int> gt[100001];
vector <int> ctc[100001];
stack <int> s;
int dfs(int k)
{ vector <int>::iterator it;
  v[k]=1;
  for(it=g[k].begin();it!=g[k].end();it++)
  { int vf;
    vf=(*it);
    if(v[vf]==0)
       dfs(vf);
  }
  s.push(k);
}
int dfst(int k)
{ vector <int>::iterator it;
  v[k]=1;
  ctc[r].push_back(k);
  for(it=gt[k].begin();it!=gt[k].end();it++)
  { int vf;
    vf=(*it);
    if(v[vf]==0)
       dfst(vf);
  }
  s.push(k);
}
int main()
{ in>>n>>m;
  for(int i=1;i<=m;i++)
  { in>>a>>b;
    g[a].push_back(b);
    gt[b].push_back(a);
  }
  for(int i=1;i<=n;i++)
    if(v[i]==0)
       dfs(i);
  for(int i=1;i<=n;i++)
    v[i]=0;
  while(!s.empty())
  { int vf;
    vf=s.top();
    s.pop();
    if(v[vf]==0)
    { r++;
      dfst(vf);
    }
  }
  out<<r<<'\n';
  for(int i=1;i<=r;i++)
  { for(auto nod:ctc[i])
      out<<nod<<' ';
    out<<'\n';
  }
  in.close();
  out.close();
  return 0;
}