第一题__牛客网

丿沧海忘川

注意：顶点就是题目中所给的那些，不多也不少，一开始没有弄明白这个一直做不出来

使用了set，保证了元素有序和不重复，便于最后并查集的查找

#include <iostream>
#include <set>
using namespace std;
#define N 1000000
int Tree[N];
int findRoot(int x){
    if(Tree[x]==-1) return x;
    int temp=findRoot(Tree[x]);
    Tree[x]=temp;
    return temp;
}
int main(){
    int a,b;
    set<int>s;
    for(int i=0;i<N;i++) Tree[i]=-1;
    while(cin>>a>>b){
        s.insert(a);
        s.insert(b);
        a=findRoot(a);
        b=findRoot(b);
        if(a!=b) Tree[a]=b;
    }
    int ans=0;
    set<int>::iterator it;
    for(it=s.begin ();it!=s.end ();it++)
        if(Tree[*it]==-1) ans++;
    cout<<ans<<endl;
    return 0;
}

发表于 2019-03-06 16:59:43 回复(1)

漫山Ms

#include<bits/stdc++.h>
using namespace std;
/*并查集，开辟一个大数组*/
const int MAXN=1000001;
int father[MAXN];
int appear[MAXN];//1表示appear[i]出现过
void Initial()
{
    for(int i=0;i<MAXN;i++)
    {
        father[i]=-1;
        appear[i]=0;
    }
}
int Find(int x)
{
    while(father[x]!=-1)
        x=father[x];
    return x;
}
void Union(int x,int y)//根节点的合并集合
{
    x=Find(x);
    y=Find(y);
    if(x!=y)
       father[y]=x;
    return ;
}
int main()
{
    int x,y;
    Initial();
    while(cin>>x>>y)
    {
        Union(x,y);
        appear[x]=1;
        appear[y]=1;
        //x和y出现过则置为1
    }
    int component=0;
    for(int i=0;i<MAXN;i++)
        if(appear[i]==1&&father[i]==-1)
            component++;
    //因为之前合并过集合所以father[i]==-1说明有一个连通分量，且要出现过
    cout<<component<<endl;
    return 0;
}

发表于 2022-03-30 11:06:30 回复(0)

夏倾尘

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
#include <sstream>
#include<map>
using namespace std;
int fa[1000005];
bool vis[1000005];
int get(int root){
    if(fa[root]==root)
        return root;
    else
        return fa[root]=get(fa[root]);
}
int main(){
    int a,b;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=1000000;i++)
        fa[i]=i;
    while(cin>>a>>b){
        vis[a]=true;
        vis[b]=true;
        a=get(a);
        b=get(b);
        fa[a]=b;
    }
    int ans=0;
    for(int i=0;i<=1000000;i++){
        if(vis[i]==true){

            if(fa[i]==i)
                ans++;
        }
    }
    cout<<ans<<endl;
}

发表于 2021-02-06 11:09:49 回复(0)

sunX&Y

/*
*根据输入的数据生成并查集 ， 然后查询根节点的个数
*/


#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6;
int father[maxn+5];

void Initial()   //初始化父节点数组
{
    for(int i = 0;i < maxn; i++) father[i] = i;
}

int getFather(int x)   //找到根节点
{
    int a = x;
    while(x != father[x]) x = father[x];
    //路径压缩
    while(a != father[a])
    {
        int z = a; a = father[a]; father[z] = x;
    }
    return x;
}

void Union(int a, int b)   //合并
{
    int fa = getFather(a);
    int fb = getFather(b);
    if(fa != fb) father[fa] = fb;
}

int main()
{
    ios::sync_with_stdio(false);
    int a, b; set<int> s;
    Initial();
    while(cin >> a >> b)
    {
        Union(a, b); s.insert(a); s.insert(b);
    }

    int ans = 0;   
    for(int i : s) ans += father[i] == i? 1 : 0;
    cout << ans << "\n";

    return 0;
}

发表于 2021-01-19 16:04:29 回复(0)

C/C++

不考上旦大不改网名

/*题目有点SB，连个节点范围也不给说
思路很简单，判断连通分量，直接用并查集就行。
有几个根节点（father[i]==i），就有几个联通分量
*/

# include<stdio.h>
const int maxn=1000010;
bool isnode[maxn];      //记录是节点的数字
int father[maxn];
int findfather(int x){
    while(father[x]!=x)
        x=father[x];
    return x;
}
void Union(int a,int b){
    int faA=findfather(a);
    int faB=findfather(b);
    if(faA!=faB){
        father[faA]=faB;
    }
}

int main(){
    int i,j;
    int a,b;
    for(i=0;i<maxn;i++){
        isnode[i]=false;
        father[i]=i;
    }
    while(scanf("%d%d",&a,&b)!=EOF){
        isnode[a]=true;
        isnode[b]=true;
        Union(a,b);

    }
      int component=0;
    for(j=0;j<maxn;j++){
        if(isnode[j]==false) //不是节点的数字直接跳过。
            continue;
        if(father[j]==j)   //在节点中，找出根节点给个数
            component++;
    }
    printf("%d",component);

    return 0;
}

发表于 2020-03-18 11:25:14 回复(0)

榆桑

并查集思想找连通分支个数

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

map <int,int> table;
int find(int x){
	if(table.find(x)==table.end()||table[x]==x){
		return x;
	}
	else{
		table[x]=find(table[x]);  //路径压缩 
	}
	return table[x]
}

int main()
{
   int a,b;
   while(cin>>a>>b){  //读入数据，构建并查集 
       if(a==0){
       	break;
	   }
       a=find(a);
       b=find(b);
       table[a]=b;
       table[b]=b;
   }
   map<int,int>::iterator iter;
   int count=0;
   for(iter=table.begin();iter!=table.end();iter++){
   	   if(iter->second==iter->first){
   	   	    count++;
		}
   }
   cout<<count<<'\n';
}

发表于 2020-02-18 17:17:14 回复(2)

SwordSoul

这个题只有题目输入的点才有效，于是我们可以只考虑有效点；同时，点的编号与答案无关，为了防止vis过大，用map把输入的点编号 a 转化为第 i 个点，这样vis数组大小与有效点个数相等。由于未知数据量，为了节约空间，使用基于map<int, set<int> >的邻接表。最后找连通分支数，只需要dfs遍历即可。

#include<bits/stdc++.h>

using namespace std;

void dfs(bool vis[], map<int, set<int> > &ms, int i)
{
    vis[i] = 1;
    for(auto mi=ms[i].begin(); mi!=ms[i].end(); mi++){
        if(!vis[*mi]){
            dfs(vis, ms, *mi);
        }
    }
}

int main()
{
    map<int, int> m;
    map<int, set<int> > ms;
    int a, b, cnt = 0;
    while(cin>>a>>b){
        if(m.find(a) == m.end()){
            m[a] = cnt++;
            set<int> s;
            ms[m[a]] = s;
        }
        if(m.find(b) == m.end()){
            m[b] = cnt++;
            set<int> s;
            ms[m[b]] = s;
        }

        if(a != b){
            ms[m[a]].insert(m[b]);
            ms[m[b]].insert(m[a]);
        }
    }

    bool vis[cnt];
    memset(vis, 0, sizeof(vis));

    int res = 0;
    for(int i=0; i<cnt; i++){
        if(!vis[i]){
            res++;
            dfs(vis, ms, i);
        }
    }
    cout<<res;

    return 0;
}

发表于 2020-01-27 21:57:01 回复(0)

走钢索的人_

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <set>
using namespace std;
map<int, bool> visit;
map<int, vector<int> > mp;
void dfs(int x)
{
    visit[x] = 1;
    for(int i = 0;i<mp[x].size();i++)
    {
        if(!visit[mp[x][i]])
        dfs(mp[x][i]);
    }
}
int main()
{
    visit.clear();
    mp.clear();
    set<int> st;
    st.clear();
    int x,y;
    while(cin >> x >> y)
    {
        st.insert(x);
        st.insert(y);
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    int ans = 0 ;
    for(set<int>::iterator it = st.begin() ; it != st.end(); ++it)
    {
        if(visit[*it] == 0)
        {
            ans++;
            dfs(*it);
        }
    }
    cout << ans << endl;
}

发表于 2019-02-23 13:50:21 回复(0)

不应当我只是颗小药丸

/*
DFS
1.只有有边的点参与计算联通分支数，所以将vis默认为true，当有输入边时，设顶点为false，就可以只考虑有边的顶点的DFS。
2.顶点最大数量MAXN至少设置1000010。100010都不行。
*/
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN=1000010;
vector<int> Adj[MAXN];
bool vis[MAXN];
void DFS(int u)
{
    vis[u]=true;
    for(int i=0;i<Adj[u].size();i++)
    {
        int v=Adj[u][i];
        if(vis[v]==false)
            DFS(v);
    }
}
int main()
{
    fill(vis,vis+MAXN,true);
    int v1,v2;
    while(scanf("%d%d",&v1,&v2)!=EOF)
    {
        Adj[v1].push_back(v2);
        Adj[v2].push_back(v1);
        //只有有边的点参与计算联通分支数
        vis[v1]=vis[v2]=false;
    }
    int count=0;
    for(int i=0;i<MAXN;i++)
    {
        if(vis[i]==false)
        {
            DFS(i);
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}

发表于 2019-03-07 17:54:38 回复(1)

C/C++

猫猫有脾气

顶点数目必须足够大啊啊啊！！！

//const int MAX=1000010;

#include<iostream>
(720)#include<cstdio>

using namespace std;

const int MAX=1000010;
int father[MAX];
int height[MAX];
bool visit[MAX];

void Init(){
    for(int i=1;i<MAX;i++){
        father[i]=i;
        height[i]=0;
        visit[MAX]=false;
    }
}

int Find(int x){
    if(x!=father[x]){
        father[x]=Find(father[x]);
    }
    return father[x];
}
void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(height[x]<height[y]){
            father[x]=y;
        }else if(height[x]>height[y]){
            father[y]=x;
        }else{
            father[y]=x;
            height[x]++;
        }
    }
}

int main(){
    Init();
    int MaxNum=0;
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF){
        
        Union(x,y);
        visit[x]=true;
        visit[y]=true;
        MaxNum=MaxNum>x?MaxNum:x;//为了缩小下面的遍历范围 保留这一个文件中最大编号的节点
        MaxNum=MaxNum>y?MaxNum:y;
    }
    int component=0;
    for(int i=1;i<=MaxNum;i++){
        if(!visit[i])
            continue;
        if(father[i]==i)
            component++;
    }
    printf("%d\n",component);
    return 0;
}

发表于 2020-03-10 10:41:26 回复(1)

健康快乐最重要

并查集的板子，一开始不会做，后来多做了几道就差不多会了。

普通并查集只是顺序的节点号。但是本题给出的节点号不是顺序的，所以这里没有采用数组的方式，而是采用了map散列表的方式。当然通过dfs也可以很好的解决这个题目。通过对所有节点进行dfs。只要没有全遍历到，那就sum++；

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
map<int,int> father;  //通过散列表map实现的father数组
map<int,int> height;  //记录每个节点的高度
int find(int x){
    if(father.find(x)!=father.end()){
        if(father[x]!=x)
            father[x]=find(father[x]);  //路径压缩(最后自己通过例子模拟下过程)
    }
    else{//如果还没有出现的新节点。把father设成他自己(表示根节点)，height设成0
        father[x]=x;
        height[x]=0;
    }
    return father[x];
}
void Union(int a,int b){//合并函数
    a=find(a);
    b=find(b);
    if(a!=b){
        if(height[a]>height[b])
            father[b]=a;
        else if(height[b]>height[a])
            father[a]=b;
        else{
            father[a]=b;
            height[a]++;
        }
    }
}
int main()
{
    int i,j;
    while(cin>>i>>j){
        //if(i==0)break;
        Union(i,j);
    }
    int sum=0;
    for(auto it=father.begin();it!=father.end();it++){
        if(it->first==it->second)sum++;  //只要有一个父亲是本身的就说明是根节点
    }
    cout<<sum<<endl;
    return 0;   
}

编辑于 2020-02-21 13:13:57 回复(0)

liuhuiming

应该是并查集里面比较简单的，模仿大佬的写了一下，对小白比较友好的写法

#include <iostream>
#include<map>

using namespace std;

map<int, int>mp;
//map用来映射每个顶点对应的父节点是什么

int find(int x) {
    //用于找到父节点以及路径压缩
    if (x != mp[x])
    mp[x] = find(mp[x]);
    return mp[x];
}

void union_two(int A, int B) {
    int c1 = find(A);
    int c2 = find(B);
    if (c1 != c2)
        mp[c2] = c1; //若相连接的两个结点根结点不同，则合并两个根结点
}

int main() {
//这是简单的并查集的运用，因为序号不是连续的则用map映射来实现，表示存储对应的连接关系
    int a, b;
    while (cin >> a >> b) {
        if (mp.find(a) ==mp.end()) { //若已有映射中无对应的结点则存入顶点信息，并将其根节点设为自己
            mp[a] = a;
        }
        if (mp.find(b) ==mp.end()) {
            mp[b] = b;
        }
        union_two(a, b);
    }
    int cnt = 0;
//处理完所有的信息之后，再判断联通分支数为多少，其为该顶点的编号与对应父节点的编号相同的顶点的数量
    for (auto it : mp) {
        if (it.first==it.second)
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

编辑于 2024-01-19 13:05:47 回复(0)

Finalize

这道题我的思路就是利用DFS性质，跟那道判断图是否是连通的思路一样，只不过这题是统计数目。

坑点：1.这道题给定的顶点不是按序的，用数组存储会有一定问题，所以我采用map来替换visited数组

2.这道题顶点数目超级大，所以绝不能用邻接矩阵存储，另外因为我用了map,一开始按其他人讨论大小开邻接表结果内存超限了，后来测试发现只要开大小为500000的就够了

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[500000];
map<int,int> mp;
void dfs(int u){
    mp[u]=1;
    for(int i=0;i<adj[u].size();i++){
        if(mp[adj[u][i]]==0){
            dfs(adj[u][i]);
        }
    }
}
void dfsTravel(int& count){
    for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
        if(it->second==0){
            dfs(it->first);
            count++;
        }
    }
}
int main(){
    int i,j;
    //memset(visited,0,sizeof(visited));
    while(cin>>i>>j){
        adj[i].push_back(j);
        adj[j].push_back(i);
        mp[i]=mp[j]=0;
    }
    int count=0;
    dfsTravel(count);
    cout<<count<<endl;
    return 0;
}

发表于 2020-04-20 08:39:05 回复(0)

牛客978961931号

虽然运行时间长，但是能用并查集板子啊，注意题目中可能结点超过几万个

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int parent[1000000];
map<int, int> ::iterator it;
void innital(int n, map<int, int>& nodes) {//nodes在主函数，注意传参
    it = nodes.find(n);
    if (it == nodes.end()) {
        nodes[n] = 1;
        parent[n] = -1;
    }
}
int findroot(int x) {
    while (parent[x] != -1) x = parent[x];
    return x;
}
int unionset(int n1, int n2, int parent[1000000]) {
    int n1_root, n2_root;
    n1_root = findroot(n1);
    n2_root = findroot(n2);
    if (n1_root == n2_root) return 0; //同集合不用合并
    else {
        parent[n1_root] = n2_root;
        return 1;
    }
}

int main() {//统计入度为0的节点的数量。如果入度为0的节点数量大于1，则不满足树的定义。检查是否有环路存在。
    int  n1, n2;
    int k = 0;
    int flag = 1;
    map<int, int> nodes;
    map<int, int> degree;
    while (cin >> n1 >> n2) {        
            innital(n1, nodes);
            innital(n2, nodes);
            unionset(n1, n2, parent); //集合合并，合并失败有环
    }
    
        int j = 0;
        for (it = nodes.begin(); it != nodes.end(); it++) {
            int n=it->first;
            if (findroot(n)==n) j++;
        }
        cout<<j<<endl;
    return 0;
}

编辑于 2024-03-23 18:46:02 回复(0)

Python3

牛客196781578号

import sys

nodes = set()
edges = []

for line in sys.stdin:
    start, end = list(map(int, line.strip().split()))
    nodes.add(start)
    nodes.add(end)
    edges.append([start, end])
    edges.append([end, start])

nodes = list(nodes)
adjusts = {}
isvisited = {}
for node in nodes:
    adjusts[node] = []
    isvisited[node] = False

for start, end in edges:
    if start == end:
        pass
    else:
        adjusts[start].append(end)

count = 0
for node in nodes:
    if not isvisited[node]:
        count += 1
        queue = [node]
        while len(queue) > 0:
            cur = queue[0]
            queue.pop(0)
            for next_node in adjusts[cur]:
                if not isvisited[next_node]:
                    queue.append(next_node)
                    isvisited[next_node] = True

print(count)

发表于 2024-03-20 23:21:25 回复(0)

牛客698975092号

我没看错吧，数据范围啥的都没给

编辑于 2024-03-15 15:50:47 回复(0)

C++

无问西东gmy

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

set<int>vertices;                               //结点集
map<int, int>father;                            //每个结点的父亲结点
map<int, int>height;                            //每个结点的高度

//添加结点并初始化映射值
void Initial(int x) {
    if (vertices.find(x) == vertices.end()) {   //判断结点是否已存在
        vertices.insert(x);                     //向结点集中插入结点
        father[x] = x;                          //每个结点的父亲为自己
        height[x] = 0;                          //每个结点的高度为0
    }
}

int Find(int x) {                               //查找根结点
    if (x != father[x]) {                       //路径压缩
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) {                      //合并集合
    x = Find(x);
    y = Find(y);
    if (x != y) {                               //矮树作为高树的子树
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[y] < height[x]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        Initial(a);                             //添加结点
        Initial(b);                             //添加结点
        Union(a, b);                            //合并集合
    }
    int component = 0;                          //连通分量
    for (const auto& i : vertices) {
        if (Find(i) == i) {                     //集合数目
            component++;
        }
    }
    cout << component << endl;
    return 0;
}

编辑于 2024-02-21 11:30:15 回复(0)

C++

ShuChixun

我感觉有大部分人做这道题的时候就是在刷时间，甚至有的直接输出答案，建议这道题测试样例再多些。

分享一下代码

思路：构建并查集求并查集的数量

第一种使用数组 29ms 2720KB

//求连通分量 即并查集的个数
#include <cstdio>

int father[150000] = {0};
int flag[150000] = {0};//假设都未访问
int height[150000] = {0};

int Find(int x) {
    if (x != father[x])
        father[x] = Find(father[x]);
    return father[x];
}

int main() {
    int a, b;
    int num = 0;
    int max=0,min=0;
    while (scanf("%d %d", &a, &b) != EOF) {
        if (flag[a] == 0) {
            father[a] = a;
            height[a] = 1;
            flag[a] = 1;
            max=max>a?max:a;
            min=min<a?min:a;
        }
        if(a==b)
            continue;
        if (flag[b] == 0) {
            father[b] = b;
            height[b] = 1;
            flag[b] = 1;
            max=max>b?max:b;
            min=min<b?min:b;
        }
        a = Find(a);
        b = Find(b);
        //合并结点 如果根不同则加入其根节点
        if (height[a] < height[b]){
            father[a] = b;
        }
        else if (height[a] > height[b]){
            father[b] = a;
        }
        else {
            father[b] = a;
            height[a]++;
        }
    }
    //求连通分量
    for(int i=min;i<=max;i++){
        if(father[i]==i&&flag[i]==1){
            num++;
        }
    }
    printf("%d\n",num);

}

第二种比较好理解的map 省空间易于理解但是更慢了 294ms 12232KB

#include <stdio.h>
#include <map>
using namespace std;

map<int,int> father;//map保存信息
map<int,int> height;
int Find(int x) {
    if (father.find(x)!=father.end()) {
        if(father[x]!=x)
            father[x]= Find(father[x]);
    }else{
        father[x]=x;
        height[x]=1;
    }
    return father[x];
}
void Union(int x, int y) {
    //合并两棵树
    x = Find(x);
    y = Find(y);
    if (height[x] < height[y]) {
        father[x] = y;
    } else if (height[x] > height[y]) {
        father[y] = x;
    } else {
        father[y] = x;
        height[x]++;
    }
}
int main() {
    int i, j;
    while (scanf("%d%d", &i, &j) != EOF) {
        Union(i,j);
    }
    int num=0;
    for(map<int,int>::iterator it=father.begin();it!=father.end();it++){
        if(it->first==it->second)
            num++;
    }
    printf("%d\n",num);
}

发表于 2023-03-17 12:06:35 回复(1)

C++

稀有的猪

#include <cstdio>

#define maxn 1000000

int father[maxn];
int flag[maxn];

void init()
{
    for (int i = 1; i <= maxn; i++)
    {
        father[i] = i;
    }
}

int findFather(int x)
{
    while (x != father[x])
        x = father[x];
    return x;
}

void Union(int a, int b)
{
    int fa = findFather(a);
    int fb = findFather(b);
    if (fa != fb)
        father[fb] = fa;
}

int main()
{
    int x, y, cnt = 0;
    init();
    while (scanf("%d %d", &x, &y) != EOF)
    {
        Union(x, y);
        flag[x] = flag[y] = 1; 
    }
    for (int i = 1; i <= maxn; i++)
    {
        if (i == father[i] && flag[i] == 1)
            cnt++; 
    }
    printf("%d\n", cnt);
    return 0;
}

发表于 2022-03-24 21:49:34 回复(0)

C++

冲重冲冲冲

//求连通分支数即是求出连通分量
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
const int MAXIN=1000000;
int father[MAXIN];
int height[MAXIN];
bool visit[MAXIN];
void getbe(){
    for(int i=1;i<MAXIN;i++){
        father[i]=i;
        height[i]=0;
        visit[i]=false;
    }
}
int find(int x){
    while(x!=father[x]){
        x=father[x];
    }
    return x;
}
void unions(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        if(height[x]<height[y]){
            father[x]=y;
        }else if(height[x]>height[y]){
            father[y]=x;
        }else{
            father[x]=y;
            height[y]++;
        }
    }
}
int main(){
    int x,y;
    getbe();
    while(scanf("%d %d",&x,&y)!=EOF){
        unions(x,y);
        visit[x]=true;
        visit[y]=true;
    }
    int ans=0;
    for(int i=1;i<MAXIN;i++){
        if(!visit[i]){
            continue;
        }
        if(father[i]==i){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2022-03-06 10:46:23 回复(0)

第一题

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题