文章
150
粉丝
0
获赞
522
访问
22.2k
#include<bits/stdc++.h>
using namespace std;
vector<int> g[1010];//定义邻接表:g[i]存储节点i的所有邻居节点
bool vis[1000];//访问标记数组:vis[i]=true表示节点i已被DFS遍历过
void dfs(int x){
vis[x]=true;
for(int y:g[x]){ //遍历x的所有邻居y
if(!vis[y])
dfs(y);
}
}
int main(){
set<int> st;//哈希集合st,用于收集所有出现过的节点(自动去重)
int i,j;
while(cin>>i>>j){//读入边信息
st.insert(i);
st.insert(j);//将两个端点加入集合(记录有哪些节点)
g[i].push_back(j);
g[j].push_back(i);//无向图:i和j互相加入对方的邻接表
}
int ans=0;
for(int x:st){//遍历所有出现过的节点
if(!vis[x]){//如果节点x未被访问,说明发现了一个新的连通分量
ans++;
dfs(x);
}
}
cout<<ans<<endl;
return 0;
}
登录后发布评论
暂无评论,来抢沙发