https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312 其实这道题目不难,但是有很多坑点! 首先数据是性别+id,id不是数字! 输出的时候必须前面补0, 另外什么自己和自己连边
https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312
其实这道题目不难,但是有很多坑点!
首先数据是性别+id,id不是数字!
输出的时候必须前面补0,
另外什么自己和自己连边,重复的边都要注意,
更注意的是 -0000,这个数据,不能用int来读,我艹
#include <iostream> #include <map> #include <algorithm> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string> #include <string.h> using namespace std; int n; int m; struct Node { int value; int next; }edge[200005]; struct Answer { int a; int b; }res[200005]; int Compare(Answer a,Answer b) { if(a.a == b.a) return a.b < b.b; return a.a < b.a; } map<pair<int,int>,int> dic; map<pair<int,int>,int> dic2; int pos; int head[10005]; int gender[10005]; void Add(int x,int y) { edge[pos].value = y; edge[pos].next = head[x]; head[x] = pos++; } int tag; void fun(int x,int y) { tag=0; dic2.clear(); int i = head[x]; int a[305]; int j=0; while(i != -1) { if(gender[edge[i].value] == gender[x] && edge[i].value != y && edge[i].value!=x) { a[j++] = edge[i].value; } i = edge[i].next; } i = head[y]; int b[305]; int k=0; while(i!=-1) { if(gender[edge[i].value] == gender[y] && edge[i].value != x && edge[i].value!=y) { b[k++] = edge[i].value; } i = edge[i].next; } for(int p=0;p<j;p++) { for(int q=0;q<k;q++) { if(a[p]==b[q]) continue; if(dic[make_pair(a[p],b[q])]==1) { Answer s; s.a = a[p]; s.b = b[q]; res[tag++] = s; } } } sort(res,res+tag,Compare); printf("%d\n",tag); for(int i=0;i<tag;i++) { printf("%04d %04d\n",res[i].a,res[i].b); } } int main() { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); pos=0; string xx,yy; int x; int y; for(int i=0;i<m;i++) { cin>>xx>>yy; x = atoi(xx.c_str()); y = atoi(yy.c_str()); if(x<0 || xx[0]=='-') gender[abs(x)]=-1; else gender[x]=1; if(y<0 || yy[0]=='-') gender[abs(y)]=-1; else gender[y]=1; x = abs(x); y = abs(y); if(dic[make_pair(x,y)]==1) continue; Add(x,y); Add(y,x); dic[make_pair(x,y)]=1; dic[make_pair(y,x)]=1; } int k; scanf("%d",&k); for(int i=0;i<k;i++) { scanf("%d%d",&x,&y); x = abs(x); y = abs(y); fun(x,y); } return 0; }