Cod sursa(job #2115134)

Utilizator netfreeAndrei Muntean netfree Data 26 ianuarie 2018 12:59:43
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 100000 + 5;
int n, m, a, b;
vector<int> vec[N_MAX], rev[N_MAX];
bitset<N_MAX> qviz, viz;

queue<int> q;

void qdfs(int nod){
  if(qviz[nod]) return;
  qviz[nod] = true;
  q.push(nod);
  for(auto v : vec[nod])
    qdfs(v);
}

vector<int> temp;
vector<vector<int> > ans;

void dfs(int nod){
  if(viz[nod]) return;
  viz[nod] = true;
  temp.push_back(nod);
  for(auto v : rev[nod])
    dfs(v);
}

int main(){
  fin >> n >> m;
  while(m--){
    fin >> a >> b;
    vec[a].push_back(b);
    rev[b].push_back(a);
  }

  for(int i = 1; i<=n; ++i)
    if(!qviz[i])
      qdfs(i);

  while(!q.empty()){
    temp.clear();
    if(!viz[q.front()])
      dfs(q.front());
    q.pop();
    if(temp.size())
      ans.push_back(temp);
  }

  fout << ans.size() << endl;
  for(auto temp : ans){
    for (auto i : temp)
      fout << i << " ";
    fout << endl;
  }


	return 0;
}

//Andrei Muntean, 2018