Cod sursa(job #2016941)

Utilizator TincaMateiTinca Matei TincaMatei Data 30 august 2017 22:18:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;

vector<int> graph[1+MAX_N];
vector<vector<int> > tare;
int st[MAX_N], top, id[1+MAX_N], low[1+MAX_N];
bool inst[1+MAX_N];

int lastid = 1;

static inline int min(int a, int b) {
  if(a < b)
    return a;
  return b;
}

void ctc(int nod) {
  inst[nod] = true;
  st[top++] = nod;
  id[nod] = low[nod] = lastid++;
  for(auto it: graph[nod]) {
    if(id[it] == 0)
      ctc(it);
    if(inst[it])
      low[nod] = min(low[nod], low[it]);
  }
  if(low[nod] == id[nod]) {
    int tmp;
    vector<int> conex;
    do {
      tmp = st[--top];
      inst[tmp] = false;
      conex.push_back(tmp);
    } while(tmp != nod);
    tare.push_back(conex);
  }
}

int main() {
  int n, m, a, b;
  FILE *fin = fopen("ctc.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 0; i < m; ++i) {
    fscanf(fin, "%d%d", &a, &b);
    graph[a].push_back(b);
  }
  fclose(fin);

  for(int i = 1; i <= n; ++i)
    if(id[i] == 0)
      ctc(i);
  FILE *fout = fopen("ctc.out", "w");
  fprintf(fout, "%d\n", tare.size());
  for(int i = 0; i < tare.size(); ++i) {
    for(int j = 0; j < tare[i].size(); ++j)
      fprintf(fout, "%d ", tare[i][j]);
    fprintf(fout, "\n");
  }
  fclose(fout);
  return 0;
}