● Finding Connected Components in a graph through DFS

پیدا کردن مؤلفه های همبندی یک گراف (توضیح بیشتر) به وسیله ی DFS) Depth-first search) یا همان جستجوی اول سطح، یکی از برنامه های مفید برای یاد گرفتن مفاهیم گراف در برنامه نویسی است.

input

5
3
1 2
2 3
4 5

output

1 2 3
4 5

ورودی:

خط اوّل شامل عدد صحیح مثبت n (نماینده ی تعداد رأس های گراف) و خط دوّم یک عدد صحیح مثبت m (نماینده ی تعداد یال های گراف) است. که مقدار n از 100000 بیشتر نمی شود.

در m خط بعدی، در هرخط دو عدد صحیح مثبت x و y که حداکثر مقدار آنها n است داده می شود. هر x و y که در یک خط داده می شود، نشان دهنده ی این است که [اگر رئوس را نامگذاری شده فرض کنیم] رأس x در گراف به رأس y یال دارد. (یا برعکس)

خروجی:

اگر تعداد مؤلفه همبندی های این گراف را c بنامیم، در c خط به عنوان خروجی، رئوس عضو هر مؤلفه ی c_i را چاپ کنید.

// A Drop of the Programming Sea - adops.blog.ir

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define Max_n 100000
vector<int> v[Max_n];
bool mark[Max_n];

inline int DFS(int k)
{
    mark[k] = true;
    cout << k+1 << ' ';
    for(int i=0; i<v[k].size(); i++)
    {
        if(!mark[v[k][i]])
            DFS(v[k][i]);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=0; i<n; i++)
        if(!mark[i])
        {
            DFS(i);
            cout << endl;
        }
}