Cod sursa(job #2087079)

Utilizator titusTitus A titus Data 12 decembrie 2017 21:17:16
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
using namespace std;

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

int n, a[105][105], ctc[105] , viz1[105], viz2[105], nrc;

void df1(int x)
{
	viz1[x] = 1;
	for(int i =1 ; i <= n ; i ++)
		if(viz1[i] == 0 && a[x][i] == 1)
			df1(i);
}

void df2(int x) ///graful transpus
{
	viz2[x] = 1;
	for(int i =1 ; i <= n ; i ++)
		if(viz2[i] == 0 && a[i][x] == 1)
			df2(i);
}

int main()
{
    int i , j , m;
    cin >> n >> m;
    while( m-- ) {
    	cin >> i >> j;
    	a[i][j] = 1;
    }

    for(int i = 1 ; i <= n ; ++i)
        if(ctc[i] == 0){
            for(int j = 1; j <= n ; ++j)
                viz1[j] = viz2[j] = 0;
            nrc ++;
            df1(i);
        	df2(i);
            for(int j = 1; j <= n ; ++j)
                    if(viz1[j] == 1 && viz2[j] == 1)
                        ctc[j] = nrc;
		}

    cout << nrc << "\n";
    for(int i=1; i<=nrc; ++i){
        for(int j=1; j<=n; ++j)
            if (ctc[j] == i) cout << j << " ";
        cout << '\n';
    }
    return 0;
}