Cod sursa(job #599070)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 27 iunie 2011 21:48:45
Problema Paduri de multimi disjuncte Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int a[100005][100],n,m,i,c,x,y,k;
bool b[100005];

void uneste(int x, int y)
{
    a[x][++a[x][0]]=y;
}

bool da(int x, int y)
{
    if (x==y) return 1; else
    {
        b[x]=1;
        for (int i=1; i<=a[x][0]; i++)
            if (!b[a[x][i]]) if (da(a[x][i],y)) return 1;
        b[x]=0;
    }
    return 0;
}

int main()
{
    f >> n >> m;
    fill_n(b,n+1,0);
    for (i=1;i<=n; i++)
        a[i][0]=0;
    for (i=0; i<m; i++)
    {
        f >> c >> x >> y;
        if (c==1) uneste(x,y), uneste(y,x); else
        if (da(x,y)) k=0, g << "DA\n"; else k=0, g << "NU\n" ;
    }
}