Cod sursa(job #2295416)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 3 decembrie 2018 17:27:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

#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];
  }
}

void start_RoyFloyd(int n, vector<int> v[], vector<vector<int>>& ctc) {
    bitset<maxN> M[maxN];
    vector<int> w[maxN];
    // Initializare matricea drumurilor
    for (int i = 1; i<=n; ++i)
      for (int j= 1; j<=n; ++j)
        M[i][j]=0;
    for (int i = 1; i <= n; ++i) {
      M[i][i] = 1;
      for (int j = 0; j < v[i].size(); ++j) {
        M[i][v[i][j]] = 1;
      }
    }
    // Construire matricea drumurilor
    for (int k = 1; k <=n; ++k) {
      for (int i = 1; i <=n; ++i) {
        for (int j = 1; j <=n; ++j) {
          M[i][j] = M[i][j] | (M[i][k] & M[k][j]);
        }
      }
    }
    // Construire graf pentru determinarea componentelor conexe
    for (int i = 1; i <=n; ++i) {
      for (int j = 1; j <=n; ++j) {
        if (i != j) {
          if (M[i][j] & M[j][i]) { // Daca exista drum intre cele 2 noduri
            w[i].push_back(j);
            w[j].push_back(i);
          }
        }
      }
    }
    // Determinarea componentelor conexe
    vector<bool> inQ(n, 0);
    queue<int> Q;
    for (int i = 1; i <=n; ++i) {
      if (!inQ[i]) {
        ctc.push_back(vector<int>());
        Q.push(i);
        inQ[i] = 1;
        for (; !Q.empty(); Q.pop()) {
          int node = Q.front();
          ctc.back().push_back(node);
          for (vector<int>::iterator it = w[node].begin(); it != w[node].end(); ++it) {
            if (!inQ[*it]) {
              Q.push(*it);
              inQ[*it] = 1;
            }
          }
        }
      }
    }
}

void DF_Plus(const int n, vector<int> G[], vector<int>& used,
    vector<int>& discovered) {
  used[n] = true;
  for (vector<int>::iterator it = G[n].begin(); it != G[n].end(); ++it)
    if (used[*it] == false)
      DF_Plus(*it, G, used, discovered);
  discovered.push_back(n);
}

void DF_Minus(const int n, const int cnt, vector<int> G[], vector<int>& where) {
  where[n] = cnt;
  for (vector<int>::iterator it = G[n].begin(); it != G[n].end(); ++it)
    if (where[*it] == -1)
      DF_Minus(*it, cnt, G, where);
}

void start_Kosaraju(int n, vector<int> v[], vector<vector<int>>& ctc) {
  vector<int> w[maxN];
  // Graful transpus
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j < v[i].size(); ++j)
      w[v[i][j]].push_back(i);
  vector<int> discovered;
  vector<int> used;
  vector<int> where;
  used.resize(n+1);
  used.assign(n+1, 0);
  where.resize(n+1);
  where.assign(n+1, -1);
  for (int i = 1; i <= n; ++i)
    if (used[i] == 0)
      DF_Plus(i, v, used, discovered);
  int cnt = 0;
  for (; discovered.size(); discovered.pop_back()) {
    if (where[discovered.back()] == -1) {
      DF_Minus(discovered.back(), cnt, w, where);
      ++cnt;
    }
  }
  ctc.resize(cnt, vector<int>());
  for (int i = 1; i <= n; ++i) {
    ctc[where[i]].push_back(i);
  }
}

void start_Tarjan(int n, vector<int> v[], vector<vector<int>>& ctc) {
  int idx[maxN]={0}, lowlink[maxN]={0}, st[maxN]={0};
  bool inQ[maxN]={0};
  for (int i=1; i<=n; ++i)
    if (!idx[i]) Tarjan(i, v, idx, lowlink, st, inQ, ctc);
}

int main() {
  int n, m;
  vector <int> v[maxN];
  vector < vector <int> > ctc;
  citire(n,m,v);

  //start_RoyFloyd(n, v, ctc);
  //start_Kosaraju(n, v, ctc);
  start_Tarjan(n, v, 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;
}