ps个人网站怎么做,无锡专业做网站的公司有哪些,国家建设部查询网站,咨询类网站开发的意义链接#xff1a; 文章目录题目描述题解代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld题目描述 小sun最近为了应付考试#xff0c;正在复习图论#xff0c;他现在学…链接
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 32768K其他语言65536K
64bit IO Format: %lld题目描述 小sun最近为了应付考试正在复习图论他现在学到了图的遍历觉得太简单了于是他想到了一个更加复杂的问题 无向图有n个点从点1开始遍历但是规定按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法不一定能够遍历整个图所以现在小sun想问你最少加几条边可以完整的遍历整个图。 输入描述: 第一行两个整数nm代表图的点数和边数。
接下来m行每行两个整数uv代表uv有边相连无向边 输出描述: 输出一行代表最少要添加的边数。 示例1 输入
5 4
1 2
2 3
3 4
4 5输出
1示例2 输入
5 5
1 2
2 3
3 4
4 5
1 5输出
0备注: 数据范围 3≤n≤1e5, 2≤m≤1e5 1≤u,v≤n 图中点的编号从1到n。
走两步的意思 比如现在有两条边(1,2),(2,3)从1开始走只能走到1或者3。 (1-2-3),(1-2-1)
题解
首先所有点都能到达也就是图要连通不连通的话走都走不到肯定不行所以加边来连通它们。加边数就是现在存在的连通块的数量-1 都连通之后每次两步两步的走所走到的点都是偶数点而奇数点无法走到所以我们需要构造一个环使得可以通过环从偶数点迈到奇数点然后走的就全是奇数点了这样全部都走完 注意所连成的环如果是偶环通过环走到的还是偶数所以要构成奇环把一个单独隔开剩下的不就成奇数了
总结下答案就是连通块的个数0/1 如果存在奇数环就加0如果没有需要我们现构造就加1 !((vis[v] - vis[u]) 1)flag0; 如果vis[v]-vis[u]的结果ans是偶数ans1就是001所以flag0也就是v到u的距离是偶数再加上一个u到v的边就构成奇环所以不用加一表示flag0
代码
#includebits/stdc.h
#includebitset
using namespace std;
typedef long long ll;
const int maxn 100007;
struct node {int v,next;
}edge[maxn*2];
int head[maxn],cnt;
bool flag 1;
int vis[maxn];void add(int u,int v) {edge[cnt].v v;edge[cnt].next head[u];head[u] cnt;
}void dfs(int u,int fa) {vis[u] vis[fa] 1;for(int i head[u];i;i edge[i].next) {int v ;v edge[i].v;if(v fa) continue;if(vis[v]) {if(!((vis[v] - vis[u]) 1) ) flag 0;continue;}dfs(v,u);}return;
}int main() {int n,m,ans 0;cinnm;for(int i 1;i m;i) {int u,v;cinuv;add(u,v);add(v,u);}for(int i 1;i n;i) {if(vis[i]) continue;ans;dfs(i,0);}coutans - 1 flag;return 0;
}
