Cod sursa(job #2927900)

Utilizator YusyBossFares Yusuf YusyBoss Data 21 octombrie 2022 19:25:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 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;
int index_node;

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

  nsons = vsons[node].size();
  vhighestnode[node] = index_node;
  vlevel[node] = index_node;
  index_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])
        vhighestnode[node] = min(vhighestnode[node], vlevel[newnode]);
    }
    else {
      dfs(newnode, node);
      vhighestnode[node] = min(vhighestnode[node], vhighestnode[newnode]);
    }
  }

  if (vhighestnode[node] == vlevel[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);
  }

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