NC15615. 无向图的弦
描述
输入描述
输入共有 1+M+1+Q 行。
第一行有两个正整数 N,M，分别代表图的点数和边数。
接下来 M 行中的第 i 行有两个整数 xi,yi，代表此图第 i 条边的两端点。
接着有一个正整数 Q，代表有多少个询问。
最后Q 行中的第i 行有ki+1 个整数，第1 个整数是ki 代表第i 个询问的环的长度，接下来的ki 个整数vi,0,vi,1,…,vi,ki −1 代表此环的的ki 个点，对于所有0≤j<ki，点vi,j 和点vi,(j+1)mod ki 是此环中相邻的两个点。
输出描述
总共要输出 Q 行，每个询问个输出一行包含一个整数，代表第 i 个询问所给的环共有多少条「弦」。
示例1
输入:
7 10 0 1 1 2 2 3 3 4 4 5 5 6 0 6 0 3 3 6 2 5 4 7 0 1 2 3 4 5 6 5 0 3 2 5 6 5 0 1 2 5 6 3 0 3 6
输出:
3 1 0 0
C++11(clang++ 3.9) 解法, 执行用时: 1432ms, 内存消耗: 19080K, 提交时间: 2020-03-25 20:48:31
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
int x[maxn],y[maxn];
vector<int> query[maxn];
int ans[maxn];
int n,m,q,k;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&x[i],&y[i]);
scanf("%d",&q);
for(int id=1;id<=q;id++)
{
scanf("%d",&k);
ans[id]=-k;
for(int i=1;i<=k;i++)
{
int u;
scanf("%d",&u);
query[u].push_back(id);
}
}
for(int i=1;i<=m;i++)
{
auto u=query[x[i]].begin(),v=query[y[i]].begin();
while(u!=query[x[i]].end()&&v!=query[y[i]].end())
{
if(*u==*v)
{
ans[*u]++;
u++;
v++;
}
else if(*u<*v) u++;
else if(*u>*v) v++;
}
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
}