Graph
1s,256M
【题目描述】
给你一个n个点m条边的无向图，每个点都有自己的颜色Ci
V(k)是一个点集，集合里面的元素是所有颜色为k的点
定义一个集合Q(k),Q(k)={Cu:Cu!=k,如果存在一条边<u,v>,其中v属于V(k)}，通俗一点讲就是Q(k)里面的元素是与V(k)相连的点的各种颜色。注意集合里的元素是不重复的。
你的任务是找到一个最小的k，其中Q(k)是最大的。注意你找的k必须是图里存在的颜色。
【输入格式】
第一行n,m
第二行n个数，为每个点对应的颜色
接下来m行描述了一个无向图，保证无自环
【输出格式】
一个数为使Q(k)最大的k，如有多个就输出最小那个
【输入输出样例】
Input1
6 6 1 1 2 3 5 8 1 2 3 2 1 4 4 3 4 5 4 6
Output1
3
Input2
5 6 4 2 5 2 4 1 2 2 3 3 1 5 3 5 4 3 4
Output2
2
【数据约定】
60%数据，n,m,ci<=1000
100%数据: n,m,ci<=10^5
【解法】
本题有两种解法：
第一种解法：看到题目，想到图论。这么多相同颜色的点，那就缩点咯。但作为蒟蒻，TJ算法又不会，只能想想玄学的缩点方法。想想从新构图，每种颜色为一个点，比如u点和v点相连，若b【i】表示i的颜色，则在新的图中，b【u】点和b【v】点相连。最后再计算每个点的度，选取最大度的最小颜色点就行了（就是先选度最大的，如果度相同，选颜色小的）
第二种解法：想想，其实和noip2016的普及组第三题有异曲同工之妙，构造简单的链表（数组实现）链表i 表示与颜色i相连的颜色。具体实现上，f 数组存储数字，ff 数组中的 ff【i】表示ff 的后继为 f中的第i 个。然后读入，若u和v相连，若b【i】表示i的颜色，则b【u】放在链表b【v】的最后，b【v】放在链表b【u】的最后。
【代码】只写了第二种解法
#include<cstdio> #include<cstdlib> #include<iostream> #include<iomanip> using namespace std; int i,j,k,m,n,o,p,js,jl,u,v,ma,mb,nn; int a[1001][1001]; int b[100001]; int c[100001]; int f[200001]; int ff[200001]; int g[100001]; int gg[100001]={0}; int main() { FILE *fin,*fout; fin=fopen("graph.in","rb"); fout=fopen("graph.out","wb"); fscanf(fin,"%d%d",&n,&m); for(int i=1;i<=n;i++) { fscanf(fin,"%d",&b[i]); gg[b[i]]=1; if(b[i]>nn)nn=b[i]; } //========================================================== if(n<=100000) { k=0; for(int i=1;i<=m;i++) { fscanf(fin,"%d%d",&u,&v); if(b[v]!=b[u]) if(g[b[u]]!=0) { int kk=g[b[u]]; int pd=0; while (true) { if(f[kk]==b[v]) { pd=1; break; } if(ff[kk]==0)break; kk=ff[kk]; } if(pd==0) { c[b[u]]++; k++; ff[kk]=k; f[k]=b[v]; } } if(b[v]!=b[u]) if(g[b[v]]!=0) { int kk=g[b[v]]; int pd=0; while (true) { if(f[kk]==b[u]) { pd=1; break; } if(ff[kk]==0)break; kk=ff[kk]; } if(pd==0) { c[b[v]]++; k++; ff[kk]=k; f[k]=b[u]; } } if(b[v]!=b[u]) if(g[b[u]]==0) { k++; g[b[u]]=k; f[k]=b[v]; c[b[u]]++; } if(b[v]!=b[u]) if(g[b[v]]==0) { k++; g[b[v]]=k; f[k]=b[u]; c[b[v]]++; } } ma=-1; for(int i=1;i<=nn;i++) { if((c[i]>ma)&&(gg[i]==1)) { ma=c[i]; mb=i; } } } fprintf(fout,"%d",mb); fclose(fin); fclose(fout); return 0; }
