1013:
删除一个结点后保持其他结点连通性的问题
dfs遍历 看有多少划分 可能效率不是很好
#include<iostream>
using namespace std;
#include<memory.h>
int map[1001][1001];
int sto[1001][1001];
int city;
int way;
int num;
void dfs(int k)
{
sto[0][k]=1;
for(int i=1;i<=city;i++)
{
if(sto[k][i]==1&&sto[0][i]==0)
{
dfs(i);
}
}
}
int main()
{
int a;
int b;
int occupy;
int count;
cin>>city;
cin>>way;
cin>>num;
memset(map,0,sizeof(map));
for(int i=0;i<way;i++)
{
cin>>a;
cin>>b;
map[a][b]=1;
map[a][0]++;
map[b][a]=1;
map[b][0]++;
}
for(int i=0;i<num;i++)
{
memcpy(sto,map,sizeof(sto));
cin>>occupy;
count=0;
for(int i=1;i<=city;i++)
{
if(sto[occupy][i]==1)
{
sto[occupy][i]=0;
sto[i][occupy]=0;
}
}
for(int i=1;i<=city;i++)
{
if(sto[0][i]==0&&i!=occupy)
{
count++;
dfs(i);
}
}
cout<<count-1<<endl;
}
}
分享到:
相关推荐
PAT顶级题目题解,用到的算法为并查集。去掉某一个城市,先利用正在使用的公路,对各个城市进行合并。然后利用被摧毁的公路,对城市进行合并,并把所需的修复费用进行加和。
lora-l101-pAT-demo-V1.0
PAT-Noxim - NoC 模拟器 欢迎使用 PAT-Noxim,循环精确的片上网络 (NoC) 模拟器。 描述 片上网络 (NoC) 已被证明在众核架构中具有低延迟和高度可扩展性。 由于可扩展性的重要性,设计人员尝试优化整个网络的延迟、...
压缩包内直接保存的是各题源代码(题意请自行去网上查找),亲测有效
generator-pat-marionette generatorGetting Started全局安装 yeoman、grunt-cli、bowernpm install -g yonpm install -g grunt-clinpm install -g bower由于当前generator没有注册到gurnt上去,所以你要先把源文件...
dcu2pat,make Delphi .dcu to .pat!! http://redplait.blogspot.com/2013/05/dcu2pat.html I wrote today some simple hack tool for creating signatures from delphi .dcu files for IDA flair The main idea is ...
vs2010写的代码 语言c++ 1001 害死人不偿命的(3n+1)猜想 使用if语句和while语句
PAT-B1012.数字分类题目描述:给定一系列正整数,请按照要求对数字进行分类,并输出以下五类数字:A1 = 能被5整除的数字中所有偶数的和;每个测试用例先给
【PAT-B1012】数字分类——c++满分题解(csdn)————程序
【PAT-B1063 谱半径——c++满分题解】(csdn)————程序
浙江大学Programming Ability Test《数据结构学习与实验指导》实验项目集里面30道题左右的答案。 网址http://pat.zju.edu.cn/ 做PAT里面的题时,我自己写得代码。
textarea class =“ pat-tinymce” data-pat-tinymce =“ inline:false”>这是tinymce的非内联/ iframe实例。 </ textarea> < textarea class =" pat-tinymce " data-pat-tinymce =" inline: false " &...
浙江大学PAT题解(C/C++/Java/Python) - 努力成为萌萌的程序媛
主控为STM32F103,wifi模组由涂鸦提供,wifi为透传模式,stm32为主控,搭配电机,DHT11温湿度模块,触摸屏。
ts解析器, 分析ts视频的结构, 有利工具.
当正确选项是 A、B、C、D 时,分别输出 1、2、3、4。输入输出格式输入第一行给出一个正整数 N,随后 N 行,每行按照“编号-答案”的格式给出一道题的 4
【CCF CSP-202012-1】期末预测之安全指数题意概述输入输出格式输入的第一行包含一个正整数 n。接下来 n 行,每行包含用空格分隔的两个整数,分别表示
pat顶级和leetcode PAT-Basic-Level 个人准备的PAT乙级考试 不定期更新,用空就来刷刷题。。。 更新日志: 时间 题目 17.5.9 1026.cpp 1046.cpp 17.5.13 1004.cpp 1018.cpp 1041.cpp 1032.cpp 17.5.14 1036.cpp 1027...
PAT / leetcode 或其他平台。 拍 PAT(Programming algorithm test)是浙江大学创建的一个测试。 它包含三个级别:基本/高级/顶级。 这个存储库主要包括高级级别。 通常,我会在代码头中记录我在每个算法问题中消耗...
题名 Hands-On RESTful API Design Patterns and Best Practices 副标题 Design, Develop, and Deploy Highly Adaptable, Scalable, and Secure RESTful Web APIs 作者 Harihara Subramanian and Pethuru Raj ...