Cod sursa(job #2927678)

Utilizator Anastasia7Anastasia Anastasia7 Data 21 octombrie 2022 00:58:48
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

#define MAX_N 20001
#define ll long long int
using namespace std;
unsigned n, m;
ifstream f("ctc.in");
ofstream gout("ctc.out");
struct Node {
  vector < int > adj;
  vector < int > rev_adj;
};

Node g[MAX_N];

stack < int > S;
stack < int > B;
int visited[MAX_N];

unsigned component[MAX_N];
vector < int > components[MAX_N];
int numComponents;

void dfs_1(int x) {
  visited[x] = true;
  for (unsigned i = 0; i < g[x].adj.size(); i++) {
    if (!visited[g[x].adj[i]]) dfs_1(g[x].adj[i]);
  }
  S.push(x);
}
int t[MAX_N];
void dfs_2(int x) {

  t[x]=numComponents;
  component[x] = numComponents;
  components[numComponents].push_back(x);
  visited[x] = true;
  for (unsigned i = 0; i < g[x].rev_adj.size(); i++) {
    if (!visited[g[x].rev_adj[i]]) dfs_2(g[x].rev_adj[i]);
  }
}

void Kosaraju() {
  for (unsigned i = 1; i <=n; i++)
    if (!visited[i]) dfs_1(i);

  for (unsigned i = 1; i <=n; i++)
    visited[i] = false;

  while (!S.empty()) {
    int v = S.top();
    S.pop();
    if (!visited[v]) {

      dfs_2(v);
      numComponents++;

    }
  }
}

int main() {

  f >> n >> m;
  int a, b;
  while (m--) {
    f >> a >> b;
    g[a].adj.push_back(b);
    g[b].rev_adj.push_back(a);
  }

  Kosaraju();
  gout<<numComponents<<endl;
    for(unsigned i=0;i<numComponents;i++)
    {
        for(unsigned j=1;j<=n;j++)

            if(t[j]==i)
                gout<<j<<" ";
         gout<<endl;
    }

  return 0;
}