題目描述
以邊關系表示客戶間的轉賬行為,若客戶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;
}
}