Cod sursa(job #2978700)

Utilizator NiffSniffCojocaru Calin Marcu NiffSniff Data 14 februarie 2023 07:34:43
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int N = 100005;
vector<int> graph[N];
int n, m, low[N], idx, id[N], cnt;
vector<vector<int>> components;
stack<int> s;
bool on_stack[N];

void tarjan(int u) {
  low[u] = idx;
  id[u] = idx++;
  s.push(u);
  on_stack[u] = true;

  for (int i = 0; i < graph[u].size(); i++) {
    int v = graph[u][i];
    if (id[v] == -1) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (on_stack[v]) {
      low[u] = min(low[u], id[v]);
    }
  }

  if (low[u] == id[u]) {
    components.push_back(vector<int>());
    int v;
    do {
      v = s.top();
      s.pop();
      on_stack[v] = false;
      components[cnt].push_back(v);
    } while (u != v);
    cnt++;
  }
}

int main() {
  fin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    fin >> u >> v;
    graph[u].push_back(v);
  }
  memset(id, -1, sizeof id);
  for (int i = 1; i <= n; i++) {
    if (id[i] == -1) tarjan(i);
  }

  fout << cnt << endl;
}