Cod sursa(job #2050529)

Utilizator alin1999Buzatu Alin alin1999 Data 28 octombrie 2017 10:19:41
Problema Paduri de multimi disjuncte Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int n,m,q,a,b,tata[100005],plm,viz[100005];
bool ok;
vector<int>c[100005];
int main()
{
   fin>>n>>m;
   for(int i=1;i<=n;++i)
    {c[i].push_back(i);tata[i]=i;}
   for(int i=1;i<=m;++i)
   {
       fin>>q>>a>>b;
   if(q==1)
   {
           if(viz[b]==1)
           {
               plm=tata[b];
               for(int j=0;j<c[a].size();++j)
               {c[plm].push_back(c[a][j]);tata[c[a][j]]=plm;}
               viz[a]=1;
           }
           else
           {
               plm=tata[a];
               for(int j=0;j<c[b].size();++j)
               {c[plm].push_back(c[b][j]);tata[c[b][j]]=plm;}
               viz[b]=1;
           }

   }
   if(q==2)
    {ok=0;
        for(int j=0;j<c[a].size();++j)
    if(c[a][j]==b)
   {ok=1;break;}
   if(ok==1)
    fout<<"DA"<<"\n";
   else
    fout<<"NU"<<"\n";
   }
   }
    return 0;
}