Cod sursa(job #1922886)

Utilizator RaTonAndrei Raton RaTon Data 10 martie 2017 19:25:17
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
/*#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> A[100001];
vector <int> AT[100001], C[100001];
int N;
int V[100001], VT[100001], L[100001];

int df1(int x){
    vector <int> :: iterator it;
    V[x] = 1;
    for( it = A[x].begin(); it != A[x].end();it++ )
        if( V[*it] == 0 )
            df1(*it);
}
int df2(int x){
    vector <int> :: iterator it;
    VT[x] = 1;
    for( it = AT[x].begin(); it != AT[x].end();it++ )
        if( VT[*it] == 0 )
            df2(*it);
}

int main()
{
    int m, i, x, y, j, nrt;
    f >> N;
    f >> m;
    for(i = 1; i <= m; i++){
        f >> x >> y;
        A[x].push_back(y);
        AT[y].push_back(x);
    }
    nrt = 0;
    for( i = 1; i <= N; i++ ){
        if(L[i] == 0){
            nrt++;
            for(j = 1; j <= N; j++)
                V[j] = VT[j] = 0;
            df1(i);
            df2(i);
            for(j = 1; j <= N; j++)
                if(V[j] == 1 && VT[j] == 1){
                    C[nrt].push_back(j);
                    L[j] = nrt;
                }
        }
    }
    vector <int> :: iterator it;
    g << nrt << '\n';
    for(i = 1; i <= nrt;i++){
        for(it = C[i].begin(); it != C[i].end(); it++)
            g << *it << " ";
        g << '\n';
    }
    return 0;
}*/
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int n,m,i,j,v1,v2;
vector <int> A[100001];
vector <int> AT[100001];

int nrc, C[100001], VIZ1[100001], VIZ2[100001];

void df1(int v)
{
	vector <int> :: iterator it;
	int i;
	VIZ1[v]=1;
	for (it=A[v].begin();it!=A[v].end();it++)
	{
		i=(*it);
		if (VIZ1[i]==0)
			df1(i);
	}
}

void df2(int v)
{
	vector <int> :: iterator it;
	int i;
	VIZ2[v]=1;
	for (it=AT[v].begin();it!=AT[v].end();it++)
	{
		i=(*it);
		if (VIZ2[i]==0)
			df2(i);
	}
}

int main()
{
	fi>>n>>m;
	for (i=1;i<=m;i++)
	{
		fi>>v1>>v2;
		A[v1].push_back(v2);
		AT[v2].push_back(v1);
	}
	nrc=0;
	for (i=1;i<=n;i++)
		if (C[i]==0)
		{
			nrc++;
			for (j=1;j<=n;j++)
				VIZ1[j]=VIZ2[j]=0;
			df1(i);
			df2(i);
			for (j=1;j<=n;j++)
				if (VIZ1[j]==1 && VIZ2[j]==1)
					C[j]=nrc;
		}
    fo << nrc << '\n';
    for(j = 1; j <= nrc; j++){
        for (i=1;i<=n;i++)
            if( C[i] == j )
                fo<<i<<" ";
        fo << '\n';
    }
	fi.close();
	fo.close();
	return 0;
}