DFS（图的深搜）--判断图是否构成环以及对set利用迭代器插值插入set的方法

题目描述

以边关系表示客户间的转账行为，若客户1向2转账，就认为存在1指向2的边。假设从某个客户1出发，沿着其任意转账关系边查找，若最终均可以到达终止客户(不存在帐务转出的客户)，则认为客户1是安全客户；否则认为客户1是潜在风险客户。即，所有处于转账关系环中的客户以及指向环中客户的客户节点均是潜在风险客户。如下图，只有客户6是安全客户。

 

输入描述:

第一行为空格分隔的两个整数n和m。n为总客户数，m为总的转账关系边数。n不超过10000，m不超过100000。客户即表示为1到n的整数。 其后m行为所有的边关系，每一行为一条转账关系边，边描述为以逗号分隔的两个客户。

输出描述:

在同一行输出所有安全客户列表，无顺序要求。客户间以空格分隔。若客户列表为空，则输出None。详见样例。

示例1

输入

复制

6 6 1,3 2,4 2,6 3,4 4,5 5,3

输出

复制

6 #include<unordered_set> #include<vector> #include<iostream> using namespace std; int n,m; //--这道题就是考察从一个点的所有拓扑结构能否构成一个环，只要有一条路径能构成一个环，就凉凉了（不安全节点）， //--Set类型的Result是由已经构成环的这条路径上的所有点的集合。 //--Set类型的tmp是由当前路径的点构成的集合。 void help(unordered_set<int>& Result,const vector<pair<int,int>>& Vec,unordered_set<int>& tmp,int index){ int k = Vec[index].second; if(Result.count(k) == 1 || tmp.count(k) == 1){ Result.insert(tmp.begin(),tmp.end()); return; } else{ tmp.insert(k); for(int i = 0;i < m;i ++){ if(Vec[i].first == k){ help(Result,Vec,tmp,i); } } return; } } int main(){ cin >> n >> m; vector<pair<int,int>> Vec(m); for(int i = 0;i < m;i ++){ int Start,End; char Waste; cin >> Start >> Waste >> End; pair<int,int> tmp = make_pair(Start,End); Vec[i] = tmp; } unordered_set<int> Result; unordered_set<int> tmp; for(int i = 0;i < m;i ++){ tmp.insert(Vec[i].first); help(Result,Vec,tmp,i); tmp.clear(); } if(Result.size() == n){ cout << "None" <<endl; return 0; } else{ vector<int> out; for(int i = 1;i <= n;i ++){ if(Result.count(i) != 1){ out.push_back(i); } } for(int i = 0;i < out.size() - 1;i ++){ cout <<out[i] << " "; } cout << out[out.size() - 1] ; return 0; } }