Cod sursa(job #2293714)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 1 decembrie 2018 14:44:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>

#define maxN 100001

using namespace std;

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

void citire(int &n, int &m, vector<int> v[]) {
  int x,y;
  fin>>n>>m;
  for (int i=1; i<=m; ++i) {
    fin>>x>>y;
    v[x].push_back(y);
  }
}

void Tarjan(int x, vector<int> v[], int idx[], int lowlink[], int st[], bool inQ[], vector<vector<int>>& ctc) {
  st[++st[0]]=x;
  inQ[x]=true;
  idx[x]=++idx[0];
  lowlink[x]=idx[0];
  for (int i=0; i<v[x].size(); ++i) {
    if (!idx[v[x][i]]) Tarjan(v[x][i], v, idx, lowlink, st, inQ, ctc);
      if (inQ[v[x][i]])
        lowlink[x] = min(lowlink[x], lowlink[v[x][i]]);
  }
  if (idx[x]==lowlink[x]) {
    ctc.push_back(vector <int>());
    while (st[st[0]]!=x) {
      ctc.back().push_back(st[st[0]]);
      inQ[st[st[0]]]=false;
      --st[0];
    }
    ctc.back().push_back(x);
    inQ[x]=false;
    --st[0];
  }
}

int main() {
  int n, m;
  vector <int> v[maxN];
  vector < vector <int> > ctc;
  bool inQ[maxN]={0};
  int idx[maxN]={0}, lowlink[maxN]={0}, st[maxN]={0};
  citire(n,m,v);
  for (int i=1; i<=n; ++i)
    if (!idx[i]) Tarjan(i, v, idx, lowlink, st, inQ, ctc);
  fout<<ctc.size()<<'\n';
  for (int i=0; i<ctc.size(); ++i) {
    for (vector <int>::iterator it=ctc[i].begin(); it!=ctc[i].end(); ++it)
      fout<<*it<<' ';
    fout<<'\n';
  }
  return 0;
}