【Link】:https://csacademy.com/contest/round-37/task/reconstruct-graph/statement/
【Description】
给你一张图;
包含n个点;m条边;
你可以在这张图的基础上添加边(不能有重边和自环);
使得节点1到节点i的最短距离为d[i]
问你可能的图的个数;
【Solution】
对于某一个节点x;
它只能和d的值为d[x]-1或者d[x]的节点直接相连
因为,d的值相同的x和y,如果它们俩之间连一条边的话,它们到节点1的距离是不会变的;
而每个节点x;
它必然要和一个d值为d[x]-1的点相连;
不然,就不能得到x的d值为d[x]了;
x节点是不能和d值小于d[x]-1的点相连的,因为那样x的d值就会小于d[x];
这样;
对于x,考虑每一个d值为d[x]-1的点,(设总数为cnt),要么和它连,要么不连;
如果原图上,x和d值为d[x]-1的点,没有一个点相连,那么就要去除全都不连的情况,不然就错了,所以乘上2cnt−1
如果原图上,x和d值为d[x]-1的点,有temp个已经相连了;(temp>0)
则乘上2cnt−temp
然后,d的值相同的点之间,可以任意相连;
设d值为i的节点个数为bo[i],然后他们之间在原图上已经有temp条边;
则答案乘上2(bo[i]∗(bo[i]−1)2−temp)
即每条边也都能选择连或不连
之后,考虑无解的情况;
如果d[i]出现了,而d[i]-1却没出现;
那么就无解;
如果d的值为0的点的个数大于1个,则无解;
如果原图上的一条边x->y
1<|d[x]−d[y]|
则也无解
【NumberOf WA】
1
【Reviw】
构造题,一般有明显的结论的;
没多想,就跳过了;
【Code】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e5;
const LL MOD = 1e9+7;
int n,m,d[N+10],bo[N+10],num_edge[N+10],ma = 0;
vector <int> g[N+10];
bool wujie(){
rep1(i,1,n)
{
int len = g[i].size();
rep1(j,0,len-1){
int y = g[i][j];
if ( abs(d[y]-d[i])>1) return true;
}
}
rep1(i,1,n) {
bo[d[i]]++;
ma = max(ma,d[i]);
}
rep1(i,0,ma)
if (!bo[i]) return true;
if (bo[0]>1) return true;
return false;
}
LL Pow(LL x,LL y){
LL temp = 1;
while (y){
if (y&1){
temp = (temp*x)%MOD;
}
x = (x*x)%MOD;
y>>=1;
}
return temp;
}
int main(){
//Open();
//Close();
scanf("%d%d",&n,&m);
rep1(i,1,n)
scanf("%d",&d[i]);
rep1(i,1,m){
int x,y;
scanf("%d%d",&x,&y);
g[x].pb(y);
g[y].pb(x);
}
if (wujie()) {
printf("0\n");
return 0;
}
//计算同层内的边有多少条,顺便计算可能方案;
rep1(i,1,n){
int len = g[i].size();
rep1(j,0,len-1){
int y = g[i][j];
if (i < y && d[i]==d[y]){
num_edge[d[i]]++;
}
}
}
LL ans = 1;
//计算和d[i]-1层的点有多少条边,顺便计算可能方案;
rep1(i,1,n)
if (i!=1){
int len = g[i].size(),temp = 0;
rep1(j,0,len-1){
int y = g[i][j];
if (d[y] == d[i]-1){
temp++;
}
}
int remain = bo[d[i]-1]-temp;
if (temp==0){
ans = ans*(Pow(2,remain)-1)%MOD;
}else{
ans = ans*Pow(2,remain)%MOD;
}
}
//计算每一层可以连的边
rep1(i,0,ma){
ans = ans*Pow(2,1LL*bo[i]*(bo[i]-1)/2 - num_edge[i])%MOD;
}
printf("%lld\n",ans);
return 0;
}
/*
写完之后,明确每一步的作用
*/