Cod sursa(job #2928479)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 22 octombrie 2022 23:40:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAXN = 100000;
const int MAXM = 100000;

vector<int> graph[MAXN];
vector<int> reverseGraph[MAXN];
vector<int> nodesOrder;
vector<int> component[MAXN];
int componentSize;
bool marked[MAXN];

void addEdge( int x, int y ){
  graph[x].push_back(y);
  reverseGraph[y].push_back(x);
}

void dfs( int root, vector<int>& path, vector<int> myGraph[MAXN]){
  marked[root] = 1;
  int i;
  //cout<<root<<'\n';
  for( i = 0; i < myGraph[root].size(); i++ ){
    if( marked[myGraph[root][i]] == 0 )
      dfs( myGraph[root][i], path, myGraph); 
  }
  path.push_back(root);
}

void resetMarked( int n ){
  int i;
  for( i = 0; i < n; i++ )
    marked[i] = 0;
}

int main(){
  int n, m, i, j, x, y, root;
  in>>n>>m;
  for( i = 0; i < m; i++ ){
    in>>x>>y;
    addEdge( x - 1, y - 1 );
  }

  // for( i = 0; i < n; i++ ){
  //   out<<i + 1<<'\n';
  //   for( j = 0; j < graph[i].size(); j++ ){
  //     out<<graph[i][j] + 1<<" ";
  //   }
  //   out<<'\n';
  // }

  for( i = 0; i < n; i++ ){
    if( marked[i] == 0 )
      dfs(i, nodesOrder, graph);
  }

  resetMarked(n);

  // for( i = 0; i < nodesOrder.size(); i++ ){
  //   out<<nodesOrder[i]<<" ";
  // }
  // out<<'\n';
  
  while( nodesOrder.size() ){
    root = nodesOrder[nodesOrder.size() - 1];
    nodesOrder.pop_back();

    if( marked[root] == 0 ){
      dfs(root, component[componentSize], reverseGraph);
      componentSize++;
    }
  }

  out<<componentSize<<'\n';
  for( i = 0; i < componentSize; i++ ){
    for( j = 0; j < component[i].size(); j++ ){
      out<<component[i][j] + 1<<" ";
    }
    out<<'\n';
  }
  return 0;
}