Cod sursa(job #1861468)

Utilizator smereniesmerenie smerenie Data 28 ianuarie 2017 21:51:20
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int a[10001][10001], at[10001][10001],n, m, viz[10001], nrcc, k, v[10001];

void citire()
{
	f>>n>>m;
	int i, x, y;
	for (i = 1; i <= m; i++)
	{
		f>>x>>y;a[x][y] = at[y][x] = 1;
	}
}

void DFS1(int nod) //parcurgerea in adancime
{
	viz[nod] = 1;
	for (int i = 1; i <= n; i++)
          if (!viz[i] && a[nod][i]) DFS1(i);
}

void DFS2(int nod) //parcurgerea in adancime
{
	viz[nod] = 1;
	for (int i = 1; i <= n; i++)
          if (!viz[i] && a[nod][i]) DFS2(i);
    g<<nod<<' ';
}

void DFS_transp(int nod) //parcurgerea in adancime
{
	viz[nod] = 1;
	for (int i = 1; i <= n; i++)
          if (!viz[i] && at[nod][i]) DFS_transp(i);
    v[++k]=nod;
}

int main()
{
    citire();int i;
    //cautarea in adancime pe graful transpus
    for(i=1;i<=n;i++)
        if(!viz[i]) DFS_transp(i);
    //resetare vector viz
    for(i=1;i<=n;i++) viz[i]=0;
    //parcurgerea in adancime pe graful initial si numarare componente
    for(i=n;i>=1;i--)
        if(!viz[i])
           {nrcc++;DFS1(v[i]);}
    g<<nrcc<<'\n';
    //parcurgerea in adancime pe graful initial si afisare componente
    for(i=1;i<=n;i++) viz[i]=0;
    for(i=n;i>=1;i--)
        if(!viz[i])
    {
        DFS2(v[i]);g<<'\n';
    }
    f.close();g.close();return 0;
}