注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Croc Champ 2013 - Round 1 D. Connected Components  

2013-04-16 18:59:39|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题意:
输入n和m,n个点,m条无向边,接下里输入m条边,然后有k个操作,每个操作输入l和r,表示去掉第l到r条边(包括l和r),问剩下的图中有几个联通块。
题解:
解1:
并查集。n最大到500,m最大到10000,k最大到20000,比赛时没想出来该怎么优化。后来看了大牛的代码,分析了下具体做法:
把m条边从1遍历到m进行一次并查集,然后从m遍历到1进行一次并查集,两遍并查集找出所有能够连接两个不同联通块的边;
然后k个操作,每个操作 根据这些筛选出来的边进行一次并查集,输出结果。

/*
* test.cpp
*
* Created on: 2013-04-16
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 10010
struct Edge{
int a,b;
}edge[N];
int n,m,num,f[N],r[N];
bool vis[N];

int Find(int a)
{
if(a != f[a])
f[a]=Find(f[a]);
return f[a];
}

void fun()
{

//两遍并查集,筛选出能够连接两个不同联通块的边,存入数组r,边数为num

int i;
num=0;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
{
int x=Find(edge[i].a);
int y=Find(edge[i].b);
if(x != y)
{
r[num++]=i;
vis[i]=true;
f[x]=y;
}
}

for(i=1;i<=n;i++)
f[i]=i;
for(i=m;i>=1;i--)
{
int x=Find(edge[i].a);
int y=Find(edge[i].b);
if(x != y)
{
if(!vis[i])
{
r[num++]=i;
vis[i]=true;
}
f[x]=y;
}
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testin.txt","w",stdout);
#endif
int i,k,res,lef,rig;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&edge[i].a,&edge[i].b);
vis[i]=false;
}
fun();
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&lef,&rig);
for(i=1;i<=n;i++)
f[i]=i;
for(i=0;i<num;i++)
{
if(r[i]<=rig && r[i]>=lef)
continue;
int x=Find(edge[r[i]].a);
int y=Find(edge[r[i]].b);
if(x != y)
f[x]=y;
}
res=0;
for(i=1;i<=n;i++)
if(i == f[i])
res++;
printf("%d\n",res);
}
return 0;
}



解2:
也可以利用邻接矩阵进行dfs(注意下邻接矩阵的使用),可以AC,但是略慢。。。

/*
* test.cpp
*
* Created on: 2013-04-16
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 510
int vis[N];
vector < pair<int,int> > g[N];//定义邻接矩阵,存储边(pair第二个参数存储边的编号,pair第一个参数和g[i][j]的i分别是该边的两个端点)

void dfs(int cnt,int lef,int rig)
{
vis[cnt]=1;
for(int i=0;i<(int)g[cnt].size();i++)
{
if(g[cnt][i].second >= lef && g[cnt][i].second <= rig)//如果边不符合条件则continue
continue;
int nex=g[cnt][i].first;
if(!vis[nex])
dfs(nex,lef,rig);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testin.txt","w",stdout);
#endif
int n,m,i,k,res,lef,rig,u,v;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
g[u].push_back(make_pair(v,i));//存储边以及边的编号
g[v].push_back(make_pair(u,i));
}
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&lef,&rig);
memset(vis,0,sizeof(vis));
for(i=1,res=0;i<=n;i++)
if(!vis[i])
{
dfs(i,lef,rig);
res++;
}
printf("%d\n",res);
}
return 0;
}


  评论这张
 
阅读(81)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018