CMB12. 潜在风险客户识别
描述
输入描述
第一行为空格分隔的两个整数n和m。n为总客户数，m为总的转账关系边数。n不超过10000，m不超过100000。客户即表示为1到n的整数。输出描述
在同一行输出所有安全客户列表，无顺序要求。客户间以空格分隔。若客户列表为空，则输出None。详见样例。示例1
输入:
6 6 1,3 2,4 2,6 3,4 4,5 5,3
输出:
6
C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2018-08-30
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void help(set<int> &res,vector<pair<int,int>> vec,set<int> tmp,int index,int m)
{
int k=vec[index].second;
if(res.count(k)==1||tmp.count(k)==1)
{
res.insert(tmp.begin(),tmp.end());
return;
}
else
{
tmp.insert(k);
for(int i=0;i<m;i++)
{
if(vec[i].first==k)
{
help(res,vec,tmp,i,m);
break;
}
}
}
return;
}
int main()
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> vec(m);
for(int i=0;i<m;i++)
{
pair<int,int> tmp;
char waste;
cin>>tmp.first>>waste>>tmp.second;
vec[i]=tmp;
}
set<int> res;
set<int> tmp;
for(int i=0;i<m;i++)
{
tmp.insert(vec[i].first);
help(res,vec,tmp,i,m);
tmp.clear();
}
int size=res.size();
if(size==n)
cout<<"None";
else
{
vector<int> out;
for(int i=1;i<=n;i++)
{
if(res.count(i)!=1)
out.push_back(i);
}
int len=out.size();
for(int i=0;i<len-1;i++)
{
cout<<out[i]<<" ";
}
cout<<out[len-1];
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-30
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, u, v;
scanf("%d%d", &n, &m);
vector<int> d(n+1, 0), r;
vector<int> G[n+1];
while(m--){
scanf("%d,%d", &u, &v);
G[v].push_back(u);
d[u]++;
}
int i=0;
while(true){
for(i=1;i<=n;i++)
if(d[i]==0)
break;
if(i==n+1)
break;
d[i] = -1;
r.push_back(i);
for(auto &e: G[i])
d[e]--;
}
if(r.size()==0)
puts("None\n");
else{
sort(r.begin(), r.end());
for(i=0;i<r.size();i++)
if(i==0)
printf("%d", r[i]);
else
printf(" %d", r[i]);
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-09-10
//c库
#include <cstdio>//cio
#include <cassert>//断言
#include <cstddef>//大小类型
#include <cstdlib>//杂项
#include <cctype>//字符分类
#include <cstring>//字符串处理
#include <cmath>//数学
#include <clocale>//本地化
#include <cstdint>//类型扩展
#include <ctime>//时间
#include <cstdarg>//变长参数
//io相关
#include <iostream>//c++io
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::flush;
using std::ends;
using std::ios_base;
using std::istream;
using std::ostream;
#include <sstream>//字符串io
using std::istringstream;
using std::ostringstream;
using std::stringstream;
#include <fstream>//文件io
using std::ifstream;
using std::ofstream;
using std::fstream;
#include <iomanip>//高级io
//泛型相关
#include <type_traits>//类型处理
using std::enable_if;
#include<limits>//数值极限
using std::numeric_limits;
#include <numeric>//数值算法
#include <algorithm>//算法
#include <initializer_list>//列表
using std::initializer_list;
#include <utility>//基础容器
using std::swap;
using std::pair;
using std::make_pair;
using std::piecewise_construct;
using std::declval;
#include <tuple>//元组
using std::tuple;
using std::tuple_size;
using std::tuple_element;
using std::make_tuple;
//using std::tie;
using std::forward_as_tuple;
using std::ignore;
#include <functional>//函数
using std::function;
using std::hash;
//using std::ref;
//using std::cref;
namespace placeholders = std::placeholders;
#include <iterator>//迭代器
using std::iterator_traits;
using std::reverse_iterator;
using std::move_iterator;
using std::make_move_iterator;
using std::back_insert_iterator;
using std::back_inserter;
using std::front_insert_iterator;
using std::front_inserter;
using std::insert_iterator;
using std::inserter;
//容器相关
#include <string>//字符串
using std::string;
using std::wstring;
using std::u16string;
using std::u32string;
#include <vector>//向量
using std::vector;
#include <array>//数组
using std::array;
#include <deque>//双向向量
using std::deque;
#include <list>//链表
using std::list;
#include <set>//稳定排序二叉树
//using std::set;
using std::multiset;
#include <map>//稳定排序二叉树对
//using std::map;
using std::multimap;
#include <unordered_set>//哈希表
using std::unordered_set;
using std::unordered_multiset;
#include <unordered_map>//哈希表对
using std::unordered_map;
using std::unordered_multimap;
#include <queue>//队列
using std::priority_queue;
//工具类相关
#include <memory>//内存
using std::shared_ptr;
using std::make_shared;
using std::unique_ptr;
//using std::make_unique;
#include <exception>//异常
using std::exception;
#include <stdexcept>//更多异常
using std::runtime_error;
#include <random>//随机数
using std::default_random_engine;
using std::mt19937;
using std::mt19937_64;
using std::random_device;
using std::uniform_int_distribution;
using std::uniform_real_distribution;
using std::discrete_distribution;
#include <ratio>//比例
using std::ratio;
#include <complex>//复数
using std::complex;
#include <regex>//正则表达式
using std::regex;
using std::wregex;
using std::regex_error;
using std::cmatch;
using std::smatch;
using std::wcmatch;
using std::wsmatch;
using std::cregex_iterator;
using std::sregex_iterator;
using std::wcregex_iterator;
using std::wsregex_iterator;
using std::csub_match;
using std::ssub_match;
using std::wcsub_match;
using std::wssub_match;
//跨平台相关
#include <locale>//本地化
#include <chrono>//时钟
using std::chrono::time_point;
using std::chrono::time_point_cast;
using std::chrono::duration;
using std::chrono::duration_cast;
using std::chrono::system_clock;
using std::chrono::steady_clock;
namespace chrono = std::chrono;
#include <thread>//线程
using std::thread;
namespace this_thread = std::this_thread;
#include <mutex>//互斥
using std::mutex;
using std::timed_mutex;
using std::recursive_mutex;
using std::recursive_timed_mutex;
using std::lock_guard;
using std::unique_lock;
using std::defer_lock;
using std::try_to_lock;
using std::adopt_lock;
using std::once_flag;
#include <condition_variable>//线程同步
using std::condition_variable;
using std::condition_variable_any;
using std::cv_status;
#include <future>//期货
using std::future;
using std::shared_future;
#include <atomic>//原子库
using std::atomic;
using std::atomic_flag;
using std::memory_order;
using std::memory_order_relaxed;
using std::memory_order_consume;
using std::memory_order_acquire;
using std::memory_order_release;
using std::memory_order_acq_rel;
using std::memory_order_seq_cst;
using Graph = vector<vector<int>>;
template<typename Ty>
using WeightGraph = vector<vector<pair<int, Ty>>>;
//有向图判环、拓扑排序、求强连通分量
//返回是否无环，pTps内返回按拓扑排序的节点号，pScnn返回每个节点属于强连通分量的编号从0开始
void KosarajuDfs(Graph &graph, int node, vector<int> *pTps, vector<int> &vis, bool &bCir)
{
vis[node] = 1;
for(int dst: graph[node]) {
if(vis[dst]==0)
KosarajuDfs(graph, dst, pTps, vis, bCir);
else if(vis[dst]==1)
bCir = false;
}
vis[node] = 2;
if(pTps)
pTps->push_back(node);
}
void KosarajuDfsRev(Graph &graph, int node, vector<int> &scnn, int idx)
{
scnn[node] = idx;
for(int dst: graph[node]) {
if(scnn[dst]==-1)
KosarajuDfsRev(graph, dst, scnn, idx);
}
}
bool Kosaraju(Graph &graph, vector<int> *pTps= nullptr, vector<int> *pScnn= nullptr)
{
int n = graph.size();
bool bCir = true;
vector<int> tps;
if(pTps==nullptr && pScnn)
pTps = &tps;
if(pTps) {
pTps->clear();
pTps->reserve(n);
}
vector<int> vis(n, 0);
//正向遍历
for(int src=0; src<n; ++src) {
if(vis[src]==0)
KosarajuDfs(graph, src, pTps, vis, bCir);
}
//求拓扑排序
if(pTps)
std::reverse(pTps->begin(), pTps->end());
//反向找强连通分量
if(pScnn) {
pScnn->assign(n, -1);
Graph rev(n);
for(int i=0; i<n; ++i) {
for(int j: graph[i])
rev[j].push_back(i);
}
int idx = 0;
for(int src: *pTps) {
if((*pScnn)[src]==-1) {
KosarajuDfsRev(rev, src, *pScnn, idx);
++ idx;
}
}
}
return bCir;
}
void Dfs(Graph &graph, int node, vector<int> &flag)
{
flag[node] = 1;
for(auto dst: graph[node]) {
if(flag[dst]==0)
Dfs(graph, dst, flag);
}
}
void InitDfs(Graph &graph, vector<int> start, vector<int> &flag)
{
int n = graph.size();
for(int src=0; src<n; ++src) {
if(start[src]==1)
continue;
if(flag[src]==0)
Dfs(graph, src, flag);
}
}
void Func(Graph graph)
{
int n = graph.size();
vector<int> node;
Kosaraju(graph, nullptr, &node);
vector<int> nodeNum, from;
for(int i=0; i<n; ++i) {
if(nodeNum.size()<=node[i]) {
nodeNum.resize(node[i]+1, 0);
from.resize(node[i]+1, 0);
}
++ nodeNum[node[i]];
from[node[i]] = i;
}
int n2 = nodeNum.size();
vector<std::set<int>> graphTmp(n2);
for(int u=0; u<n; ++u) {
for(auto v: graph[u]) {
if(node[v]!=node[u])
graphTmp[node[v]].insert(node[u]);
}
}
Graph graph2(n2);
for(int u=0; u<n2; ++u) {
for(auto v: graphTmp[u]) {
graph2[u].push_back(v);
}
}
vector<int> flag(n2, 0);
InitDfs(graph2, nodeNum, flag);
vector<int> ret;
for(int i=0; i<n2; ++i) {
if(flag[i]==0)
ret.push_back(from[i]);
}
std::sort(ret.begin(), ret.end());
for(int i=0; i<ret.size(); ++i) {
if(i!=0)
cout <<" ";
cout <<ret[i]+1;
}
if(ret.empty())
cout <<"None";
}
int main()
{
int n, m;
Graph graph;
#ifdef DEBUG
graph.resize(6);
graph[0] ={2};
graph[1] ={3, 5};
graph[2] ={3};
graph[3] ={4};
graph[4] ={2};
graph[5] ={};
#else
cin >>n >>m;
graph.resize(n);
for(int i=0; i<m; ++i) {
int tmp1, tmp2;
char ch;
cin >>tmp1 >>ch >>tmp2;
graph[tmp1-1].push_back(tmp2-1);
}
#endif
Func(graph);
}
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2020-09-10
#include "stdio.h"
#include <vector>
#include <map>
#include "string.h"
#include "algorithm"
using namespace std;
int main(){
int n,m;
scanf("%d %d",&n,&m);
// printf("%d %d",n,m);
//vector<vector<int > > v(n+2,vector<int>());
vector<int > de(n+2,0);
map<int,vector<int>> v;
int i,j,k,l;
while(m--){
scanf("%d,%d",&k,&l);
// printf("%d,%d\n",k,l);
if(v.count(l)==0)
v[l] = vector<int>{};
v[l].push_back(k);
de[k]++;
}
vector<int> res;
k=0;
while(true){
for(i=1;i<=n;i++){
if(de[i]==0)break;
}
if(i==n+1)break;
de[i]=-1;
res.push_back(i);
for(j=0;j<v[i].size();j++){
de[v[i][j]]--;
}
}
if(res.size()==0)printf("None\n");
else{
sort(res.begin(),res.end());
printf("%d",res[0]);
for(i=1;i<res.size();i++){
printf(" %d",res[i]);
}
printf("\n");
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-11-15
/*
1.以邻接矩阵的方式存储数据；
2.没有出边的元素一定表示安全客户；
3.找到没有出边的元素（弧头）后，保存该元素，再将邻接矩阵中包含该弧头的对应的边置零；
4.检查邻接矩阵有没有变化（flag的作用），有变化则重复3，无变化则得到结果。
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int D[10001][10001] = { 0 };
int out[10010]={0};
bool judge(int indx, int n)//判断某点是否有出边,有则返回false
{
for (int k = 1; k < n + 1; k++)
if (D[indx][k] == 1)
return false;
return true;
}
int main()
{
int n,m;
cin >> n>>m;
for (int i = 0; i < m; i++)
{
int a, b;
char c;
cin >> a >>c >> b;
D[a][b] = 1;
}
vector<int> result;
while (1)
{
bool flag = 0;
for (int i = 1; i <= n; i++)
{
if (judge(i,n) && find(result.begin(),result.end(),i)== result.end())
{
flag = 1;
result.push_back(i);
for (int k = 1; k <= n; k++)
if (D[k][i] == 1)D[k][i] = 0;
}
}
if (!flag)break;
}
int s = result.size();
if (s == 0)
cout << "None" << endl;
else
{
sort(result.begin(), result.end());
for (int i = 0; i < s - 1; i++)
{
cout << result[i] << " ";
}
cout << result[s - 1];
}
return 0;
}