Cod sursa(job #1438741)

Utilizator S7012MYPetru Trimbitas S7012MY Data 20 mai 2015 18:54:23
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#define DN 100005
using namespace std;

typedef vector<int>::iterator it;

int n,m,h[DN],lw[DN];
vector<int> gr[DN],st;
vector<vector<int> > r;
bitset<DN> viz;

void d(int s,int hc) {
  h[s]=lw[s]=hc; viz[s]=1;
  st.push_back(s);
  for(it i=gr[s].begin(); i!=gr[s].end(); ++i) {
    if(!viz[*i])
      d(*i,hc+1);
    lw[s]=min(lw[s],lw[*i]);
  }
  if(lw[s]==h[s]) {
    vector<int> cc;
    int tp;
    do {
      tp=st.back(); st.pop_back();
      cc.push_back(tp);
    }while(tp!=s);
    r.push_back(cc);
  }
}

int main() {
  ifstream f("ctc.in");
  ofstream g("ctc.out");
  for(f>>n>>m;m--;) {
    int a,b; f>>a>>b;
    gr[a].push_back(b);
  }
  for(int i=1; i<=n; ++i) if(!viz[i]) d(i,0);
  g<<r.size()<<'\n';
  for(int i=0; i<r.size(); ++i) {
    for(it j=r[i].begin(); j!=r[i].end(); ++j) g<<*j<<' ';
    g<<'\n';
  }
}