[LintCode][DFS] Find the Connected Component in the Undirected Graph

Problem

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

Clarification
Learn more about representation of graphs

Example
Given graph:

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E

Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

Solution

DFS找出聯(lián)通塊

/**
 * Definition for Undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    set<int> visited;
public:
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    vector<vector<int>> connectedSet(vector<UndirectedGraphNode*>& nodes) {
        vector<vector<int>> ret;
        for(int i = 0; i < nodes.size(); i++) {
            if (visited.count(nodes[i]->label) == 0) {
                vector<int> res;
                visited.insert(nodes[i]->label);
                dfs(nodes[i], res);
                sort(res.begin(), res.end());
                ret.push_back(res);
            }
        }
        return ret;
    }
    
    void dfs(UndirectedGraphNode *node, vector<int> &res) {
        res.push_back(node->label);
        for(int i = 0; i < node->neighbors.size(); i++) {
            int label = node->neighbors[i]->label;
            if (visited.count(label) == 0) {
                visited.insert(label);
                dfs(node->neighbors[i], res);
            }
        }
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末叔磷,一起剝皮案震驚了整個濱河市续语,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌采驻,老刑警劉巖拄踪,帶你破解...
    沈念sama閱讀 211,639評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異,居然都是意外死亡纤虽,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,277評論 3 385
  • 文/潘曉璐 我一進店門绞惦,熙熙樓的掌柜王于貴愁眉苦臉地迎上來逼纸,“玉大人,你說我怎么就攤上這事济蝉〗芄簦” “怎么了?”我有些...
    開封第一講書人閱讀 157,221評論 0 348
  • 文/不壞的土叔 我叫張陵堆生,是天一觀的道長专缠。 經(jīng)常有香客問我,道長淑仆,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,474評論 1 283
  • 正文 為了忘掉前任哥力,我火速辦了婚禮蔗怠,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘吩跋。我一直安慰自己寞射,他們只是感情好,可當我...
    茶點故事閱讀 65,570評論 6 386
  • 文/花漫 我一把揭開白布锌钮。 她就那樣靜靜地躺著桥温,像睡著了一般。 火紅的嫁衣襯著肌膚如雪梁丘。 梳的紋絲不亂的頭發(fā)上侵浸,一...
    開封第一講書人閱讀 49,816評論 1 290
  • 那天,我揣著相機與錄音氛谜,去河邊找鬼掏觉。 笑死,一個胖子當著我的面吹牛值漫,可吹牛的內(nèi)容都是我干的澳腹。 我是一名探鬼主播,決...
    沈念sama閱讀 38,957評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼酱塔!你這毒婦竟也來了沥邻?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,718評論 0 266
  • 序言:老撾萬榮一對情侶失蹤羊娃,失蹤者是張志新(化名)和其女友劉穎谋国,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體迁沫,經(jīng)...
    沈念sama閱讀 44,176評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡芦瘾,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,511評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了集畅。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片近弟。...
    茶點故事閱讀 38,646評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖挺智,靈堂內(nèi)的尸體忽然破棺而出祷愉,到底是詐尸還是另有隱情,我是刑警寧澤赦颇,帶...
    沈念sama閱讀 34,322評論 4 330
  • 正文 年R本政府宣布二鳄,位于F島的核電站,受9級特大地震影響媒怯,放射性物質(zhì)發(fā)生泄漏订讼。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,934評論 3 313
  • 文/蒙蒙 一扇苞、第九天 我趴在偏房一處隱蔽的房頂上張望欺殿。 院中可真熱鬧,春花似錦鳖敷、人聲如沸脖苏。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,755評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽棍潘。三九已至,卻和暖如春崖媚,著一層夾襖步出監(jiān)牢的瞬間亦歉,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,987評論 1 266
  • 我被黑心中介騙來泰國打工至扰, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留鳍徽,地道東北人。 一個月前我還...
    沈念sama閱讀 46,358評論 2 360
  • 正文 我出身青樓敢课,卻偏偏與公主長得像阶祭,于是被迫代替她去往敵國和親绷杜。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,514評論 2 348

推薦閱讀更多精彩內(nèi)容