Cod sursa(job #2927896)

Utilizator YusyBossFares Yusuf YusyBoss Data 21 octombrie 2022 19:19:59
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;

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

vector <int> vsons[NMAX + 1];
bool is_visited[NMAX + 1];
bool found_component[NMAX + 1];
int vhighestnode[NMAX + 1];
int vlevel[NMAX + 1];
int nctc;
vector <int> vctc[NMAX + 1];
stack <int> stack_ctc;

void dfs(int node, int tata, int level) {
  int nsons, i;

  vlevel[node] = level;
  nsons = vsons[node].size();
  vhighestnode[node] = node;
  is_visited[node] = true;
  stack_ctc.push(node);
  for (i = 0; i < nsons; i++) {
    int newnode = vsons[node][i];
    if (is_visited[newnode]) {
      if (!found_component[newnode] && vlevel[vhighestnode[newnode]] <= vlevel[vhighestnode[node]])
        vhighestnode[node] = vhighestnode[newnode];
    }
    else {
      dfs(newnode, node, level + 1);
      newnode = vhighestnode[newnode];
      if (!found_component[newnode] && vlevel[vhighestnode[newnode]] <= vlevel[vhighestnode[node]])
        vhighestnode[node] = vhighestnode[newnode];
    }
  }

  if (vhighestnode[node] == node) {
    while (stack_ctc.top() != node) {
      vctc[nctc].push_back(stack_ctc.top());
      found_component[stack_ctc.top()] = true;
      stack_ctc.pop();
    }
    vctc[nctc++].push_back(node);
    found_component[node] = true;
    stack_ctc.pop();
  }
}

int main() {
  int n, m, i, j, node1, node2;
  fin >> n >> m;

  for (i = 0; i < m; i++) {
    fin >> node1 >> node2;
    vsons[node1].push_back(node2);
  }

  for (i = 1; i <= n; i++) {
    if (!is_visited[i])
      dfs(i, 0, 1);
  }

  fout << nctc << "\n";
  for (i = 0; i < nctc; i++) {
    for (j = 0; j < vctc[i].size(); j++)
      fout << vctc[i][j] << " ";
    fout << "\n";
  }
  return 0;
}