Cod sursa(job #1252817)

Utilizator Laura.miLaura Mitrache Laura.mi Data 31 octombrie 2014 12:34:19
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.95 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

 /* Solutia I

  Se memoreaza digraful si odata cu aceasta se mai memoreaza un digraf cu munchiile in sens invers
  Se face DFS din 1 pe primul graf si pe al2lea graf.
  Se verifica elementele comune, acestea apartin aceleiasi componente tare conexa;
  Apoi se reia mecanismul din primul element necomun pana cand toate componentele vor fi incadrate in cate o componenta tare conexa
  Complexitate O( m(n+m) )
  Complexitatea DFS-ului standard este O(m+n)  */

/* Solutia II , mai optim

 1. Parcurgem cu DFS digraful pentru a construi vectorul timp al timpilor finali
 2. Determinam graful transpus
 3. Apoi facem parcurgerea DFS obisnuita pe graful transpus luand nodurile in ordinea inversa din vectorul timp.
 for(i=n;i>=1;i--)
 {
    x = timp[i];
    if(tc[x] == 0)  //tc = vector de componente tare conexe
    DFS_tr(x);      //dfs pe graf transpus
 }
 La o astfel de parcurgere varfurile vizitate formeaza o componenta tare conexa
 Parcurgerea DFS pe graful transpus continua pe urmatorul nod neinclus inca pe o componenta tare conexa

 */
vector <int> L[100005];
vector <int> L_tr[100005]; //graf transpus
int m, n;
ifstream f("ctc.in");
ofstream g("ctc.out");

int timpi[100005];
int viz2[100005]; // parcurs prin DFS pe timpi finali
int viz3[100005]; // parcurs prin DFS obisnuit pe graful transpus
int k; //indice vector pe timpi finali
int tc[100005];
int z = 0; //numarul componentei conexe

void Citire()
{
    int i,x,y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {   f>>x>>y;
        L[x].push_back(y);
        L_tr[y].push_back(x);
    }
}

void DFS_Timpifinali(int x)
{
    viz2[x]=1;
    int i;
    for(i=0;i<L[x].size();i++)
        if( viz2[ L[x][i] ] == 0 )
                   DFS_Timpifinali(L[x][i]);
    timpi[++k]=x;

}

void DFS_tr(int x,int z) // DFS obisnuit pe graful transpus
{
    int i;
    viz3[x] = 1;
    tc[x]= z;

    for(i=0;i<L_tr[x].size();i++)
        if(viz3[L_tr[x][i]]==0)
                   DFS_tr(L_tr[x][i],z);

}

void Graf_Transpus()
{
    int i,j,t;
    int len;
    for(i=1;i<=n;i++)
    {
        len = L[i].size();
        for(j=0;j<len;j++)
        {
            t = L[i][j];
            L_tr[t].push_back(i);
        }
    }
}
void Afisare()
{
    int i,j;
    g<<z<<"\n";
    for(i=1;i<=z;i++)
    {
        for(j=1;j<=n;j++)
            if(tc[j] == i)
                g<<j<<" ";
        g<<"\n";
    }

}
int main()
{
    int x,j,i;
    Citire();
   // Graf_Transpus();

    for(i=1;i<=n;i++)
        if(!viz2[i])
            DFS_Timpifinali(i);

//DFS pe timpi finali
    for(i=n;i>=1;i--)
    {
        x = timpi[i];
        if(tc[x] == 0)  //tc = vector de componente tare conexe
        {
            z++;
            //for(j=0;j<=n;j++) viz3[j]=0;
            DFS_tr(x,z);      //dfs pe graf transpus
        }
    }

    Afisare();

    return 0;
}