Cod sursa(job #2839142)

Utilizator SebytomitaTomita Sebastian Sebytomita Data 25 ianuarie 2022 13:18:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.97 kb
//#include <fstream>
//#include <vector>
//#include <algorithm>
//
//#define NMAX 10004
//
//using namespace std;
//ifstream cin("componenteconexe.in");
//ofstream cout("componenteconexe.out");
//
//vector <int> a[NMAX];
//
//int n,i,j,x,y,lg,k,val,ii,nr;
//int fr[NMAX],m[104][104],scos[NMAX],cont[NMAX];
//
//int main()
//{
//    cin>>n;
//    while(cin>>x>>y)
//    {
//        if(m[x][y]==0)
//        {
//            a[x].push_back(y);
//            a[y].push_back(x);
//            m[x][y]=1;
//        }
//
//        // cout<<a[x][a[x].size()-1]<<' '<<a[y][a[y].size()-1]<<'\n';
//    }
//    for(i=1; i<=n; i++)
//    {
//        k=a[i].size()-1;
//        sort(a[i].begin(),a[i].end());
//    }
//
//    k=a[1].size();
//    for(i=0; i<k; i++)
//        fr[a[1][i]]=1;
//
//    fr[1]=1;
//
//
//
//    for(nr=1; nr<=n; nr++)
//    {
//
//        ///pt prima instanta
//        k=a[nr].size();
//        fr[nr]=1;
//        for(i=0; i<k; i++)
//            fr[a[nr][i]]=1;
//
//
//        for(ii=2; ii<=n; ii++)
//        {
//            k=a[nr].size();
//            for(i=0; i<k; i++)
//            {
//                val=a[nr][i];
//                lg=a[val].size();
//                for(j=0; j<lg; j++)
//                {
//                    if(fr[a[val][j]]==0)
//                    {
//                        //st[val]=1;
//                        a[nr].push_back(a[val][j]);
//                        fr[a[val][j]]=1;
//                    }
//                }
//            }
//        }
//    }
//
//
//    for(i=1;i<=n;i++)
//    {
//        sort(a[i].begin(),a[i].end());
//    }
//
//    nr=0;
//    for(i=1;i<=n;i++)
//    {
//        if(scos[i]==0)
//        {
//            nr++;
//            m[nr][1]=i;
//            cont[nr]=1;
//            //cout<<i<<' ';
//            k=a[i].size();
//            for(j=0;j<k;j++)
//            {
//                //cout<<a[i][j]<<' ';
//                cont[nr]++;
//                m[nr][cont[nr]]=a[i][j];
//                scos[a[i][j]]=1;
//            }
//            //cout<<'\n';
//        }
//    }
//    cout<<nr<<'\n';
//    for(i=1;i<=nr;i++)
//    {
//        for(j=1;j<=cont[i];j++)
//        {
//            cout<<m[i][j]<<' ';
//        }
//        cout<<'\n';
//    }
//
//
////    for(i=1; i<=n; i++)
////    {
////        k=a[i].size();
////        //if(st[i]==0)
////        for(j=0; j<k; j++)
////            cout<<a[i][j]<<' ';
////        cout<<'\n';
////    }
//
//
//    return 0;
//}
//

#include <fstream>
#include <vector>
#include <algorithm>

#define NMAX 100004

using namespace std;

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


///lista de adiacenta, repr ca vectori din STL
int n,m,start;

///a[x] este un vector din stl care contine lista de adiacenta a lui x
vector <int> a[NMAX];
vector <int> sol[NMAX];

int d[NMAX];
bool viz[NMAX];

void citire();
void dfs(int x,int cont);

int main()
{
    citire();
    int i,cont=0,j;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            cont++;
            dfs(i,cont);
           // cout<<'\n';
        }
    }

    cout<<cont<<'\n';

//    for(i=1;i<=cont;i++)
//    {
//        sort(sol[i].begin(),sol[i].end());
//    }
//
//    for(i=1;i<=cont;i++)
//    {
//        for(j=0;j<sol[i].size();j++)
//            cout<<sol[i][j]<<' ';
//        cout<<'\n';
//    }


    return 0;
}
void citire()
{
    int i,x,y;
    cin>>n>>m;
    while(cin>>x>>y)
    {
        ///adaug pe y in lista de adiacenta a lui x si invers
        a[x].push_back(y);
        a[y].push_back(x);
    }
}
void dfs(int x,int cont)
{
    int i;
    ///vizitez varful x
    sol[cont].push_back(x);
    //cout<<x<<' ';
    viz[x]=1;
    ///parcurg vecinii lui x
    for(i=0;i<a[x].size();i++)
    {
        if(!viz[a[x][i]]) ///vecin i nevizitat
        {
            dfs(a[x][i],cont);
        }
    }
}