Cod sursa(job #2195792)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 17 aprilie 2018 13:26:16
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.18 kb
#include <fstream>
#define nmax 100000
#define mmax 200000
using namespace std;
ifstream  fin("ctc.in");
ofstream fout("ctc.out");

int Start[nmax+2],T[2][mmax+2],visited[nmax+2];
int n,m,X[nmax+2],nX,X2[nmax+2],nX2;
int Start2[nmax+2],T2[2][mmax+2],visited2[nmax+2];

int Starttc[nmax+2],Ttc[2][mmax+2],ntc;

void DFS(int vf,int visited[nmax+2],int n,int m,
         int Start[nmax+2],int T[2][mmax+2],int X[nmax+2],int &Timp){
    int k,y;
    visited[vf]=1;
    for(k=Start[vf];k!=0;k=T[1][k]){
        y=T[0][k];///vecin cu vf
        if(visited[y]==0){
            DFS(y,visited,n,m,Start,T,X,Timp);
        }
	}
	Timp++;
	X[n+1-Timp]=vf;
}

void sortare_topologica(int n,int m,
            int Start[nmax+2],int T[2][mmax+2],
            int X[nmax+2]){
	int visited[nmax+2],k,r,j,Timp;
	for(k=1;k<=n;k++)visited[k]=0;
	Timp=0;
	for(k=1;k<=n;k++){
		if(visited[k]==0){
			///k face parte din componenta conexa noua
			DFS(k,visited,n,m,Start,T,X,Timp);
		}
	}
///X contine cele n varfuri sortate descrescator dupa timpii finali
}

void DFS2(int vf,int visited2[nmax+2],
                int n,int m,int Start2[nmax+2],int T2[2][mmax+2],
                int X2[nmax+2],int &nX2){
    int k,y;
    visited2[vf]=1;
    ///se depoziteaza in X2[] varful parcurs
    nX2++; X2[nX]=vf;
    for(k=Start2[vf];k!=0;k=T2[1][k]){
        y=T2[0][k];///vecin cu vf
        if(visited[y]==0){
            DFS2(y,visited2,n,m,Start2,T2,X2,nX2);
        }
	}
}

void determinarea_componentelor_tare_conexe(
        int n,int m,int Start2[nmax+2],int T2[2][mmax+2],
        int Starttc[nmax+2],int Ttc[2][mmax+2],int &ntc,
        int X[nmax+2],int &nX){
	int visited2[nmax+2],k,r,j,X2[nmax+2],nX2;
	for(k=1;k<=n;k++)visited2[k]=0;
	ntc=0; r=0;
	for(k=1;k<=n;k++){
		if(visited2[X[k]]==0){
			///X[k] face parte din componenta tare conexa noua
			ntc++;Starttc[ntc]=0; nX2=0;
			DFS2(k,visited2,n,m,Start2,T2,X2,nX2);
			for(j=1;j<=nX2;j++){
				r++; Ttc[0][r]=X2[j]; Ttc[1][r]=Starttc[ntc];
				Starttc[ntc]=r;
			}
		}
	}
///afisarea numarului componentelor tare conexe si a elementelor lor
	fout<<ntc<<'\n';
	for(k=1;k<=ntc;k++){
		for(j=Starttc[k];j!=0;j=Ttc[1][j]){
			fout<<Ttc[0][j]<<' ';
		}
		fout<<'\n';
	}
}
void citire_graf_orientat_liste_adiacenta(
            int &n,int &m,int Start[nmax+2],int T[2][mmax+2]){
	int i,j,k,r;
	fin>>n>>m;
	for(k=1;k<=n;k++)Start[k]=0;
	r=0;
	for(k=1;k<=m;k++){
		fin>>i>>j;
		r++;
		T[0][r]=j;///in linia 0 asezam vecinii
        ///in linia 1 asezam pozitia celui anterior
		T[1][r]=Start[i];
		Start[i]=r;
	}
}

int main(){
    citire_graf_orientat_liste_adiacenta(n,m,Start,T);
    ///sortam topologic cele n varfuri
    sortare_topologica(n,m,Start,T,X);
    ///construirea listelor de adiacenta pentru graful complementar
    for(int i=1;i<=n;i++)Start2[i]=0;
    int r=0;
    for(int k=1;k<=n;k++){
        for(int i=Start[k];i!=0;i=T[1][i]){
            r++;
            int j=T[0][i];
            T2[0][r]=k; T2[1][r]=Start2[j];
            Start2[j]=r;
        }
    }
    determinarea_componentelor_tare_conexe(n,m,Start2,T2,Starttc,Ttc,ntc,X,nX);
    fout.close(); fin.close();
    return 0;
}