Cod sursa(job #767689)

Utilizator iris88Nagy Aliz iris88 Data 14 iulie 2012 13:45:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> order;
vector<bool> visited;
vector< vector<int> > adj;
vector< vector<int> > inv;
vector<int> compon;
vector<vector<int> > ccon;
int nrcomp;
void gen_inv(int n)
{
  inv.resize(n+1);
  for (int i=1;i<=n;i++)
  {
    for (int j=0;j<adj[i].size();j++)
    {
      inv[adj[i][j]].push_back(i);
    }
  }
}
void dfs_visit(int k,vector<vector<int> > &adj,int s=0 )
{
  visited[k]= true;
  if (s!=0){
  compon[k] = s;
  ccon[s].push_back(k);
  }
  for (int i=0;i<adj[k].size();i++)
  {
    if (!visited[adj[k][i]]){      
      dfs_visit(adj[k][i],adj,s);
    }
    
  }
  order.push_back(k);
}

void dfs(int n,  vector<vector<int> > &adj)
{
  compon.resize(n+1);
  for (int i=1;i<=n;i++)
  {
    if (!visited[i])
      dfs_visit(i,adj);
  }

}
void dfs2(int n, vector<vector<int> > &adj)
{
  nrcomp=0;
  compon.resize(n+1);
  //order.resize(n+1);
  ccon.resize(n+1);
  for (int i=n-1;i>=0;i--)
  {    
    if (!visited[order[i]]){
      nrcomp++;
      dfs_visit(order[i],adj,nrcomp);
    }
  }

}
int main()
{
  FILE *f = fopen("ctc.in","r");
  FILE *g = fopen("ctc.out","w+");
  int n,m;
  fscanf(f,"%d %d", &n,&m);
  adj.resize(n+1);
  for (int i=0;i<m;i++)
  {
    int x,y;
    fscanf(f,"%d %d",&x,&y);
    adj[x].push_back(y);
  }
  visited.resize(n+1);
  for (int i=0;i<n;i++)
    visited[i]= false;
  dfs(n,adj);
  gen_inv(n);
  fill(visited.begin(),visited.end(),0);
  dfs2(n,inv);  
  fprintf(g,"%d\n", nrcomp);
  for (int i=1;i<=nrcomp;i++)
  {
    for (int j=0;j<ccon[i].size();j++)
    {
      fprintf(g,"%d ",ccon[i][j]);
    }
    fprintf(g,"\n");
  }
  fclose(f);
  fclose(g);
}