Gym - 101480J[判环+Hash]

题目链接:https://vjudge.net/problem/Gym-101480J

解题思路:

因为度最多为3所以流量最多不超过3

对于在同一个连通块上:flow ==1

对于在同一个环上(可以看做有向图强连通):flow == 2

对于某一个点对，删除任意一条边他们还是在同一个环上，说明去掉一个流量他们的流量还是2，所以这种情况:flow == 3

对于第三种情况可以枚举每条边，然后跑tarjan，再给他们Hash一下，保证只有每次都相同最后的结果才是一样的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mx = 3e3 + 10;
const ull base = 113;
int n,m,tot,head[mx];
ull be[mx];
int dfn[mx],id[mx],q[mx],is,siz;
bool vis[mx],no[mx*2];
struct node
{
int v,nxt;
}e[mx*5];
void add(int u,int v){
e[tot] = {v,head[u]};
head[u] = tot++;
e[tot] = {u,head[v]};
head[v] = tot++;
}
void dfs(int u,int c){
if(be[u]) return ;
be[u] = c;
for(int i=head[u];~i;i=e[i].nxt)
dfs(e[i].v,c);
}
void tarjan(int u,int fa){
dfn[u] = id[u] = ++is;
vis[u] = 1;
q[++siz] = u;
for(int i=head[u];~i;i=e[i].nxt){
if(i==(fa^1)||no[i>>1]) continue;
int v = e[i].v;
if(!dfn[v]){
tarjan(v,i);
id[u] = min(id[u],id[v]);
}else if(vis[v])
id[u] = min(id[u],dfn[v]);
}
if(id[u]==dfn[u]){
do{
vis[q[siz]] = 0;
be[q[siz]] = be[q[siz]]*base + u;
}while(q[siz--]!=u);
}
}
void cal(int& ans){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)
if(be[i]==be[j]) ans++;
be[i] = 0;
}
}
int main(){
scanf("%d%d",&n,&m);
int u,v;
memset(head,-1,sizeof(head));
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1,c=0;i<=n;i++)
if(!be[i]) dfs(i,++c);
int ans = 0;
cal(ans);
for(int i=1;i<=n;i++) if(!dfn[i])
tarjan(i,-1);
cal(ans);
for(int i=0;i<m;i++){
no[i] = 1,is = 0;
for(int j=1;j<=n;j++) dfn[j] = 0;
for(int j=1;j<=n;j++) if(!dfn[j])
tarjan(j,-1);
no[i] = 0;
}
cal(ans);
printf("%dn",ans);
return 0;
}

最后

以上就是过时皮皮虾为你收集整理的Gym - 101480J[判环+Hash]的全部内容，希望文章能够帮你解决Gym - 101480J[判环+Hash]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。