459 - graph connectivity solutions code example
Example: 459 - graph connectivity solutions
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[1000];
bool visited[1000];
int pre[10000];
void add(int u,int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int s)
{
if(visited[s]) return;
visited[s]=true;
for(int i=0;i<adj[s].size();i++)
{
int x=adj[s][i];
if(!visited[x]){
dfs(x);
}
}
}
int main()
{
int n,m,i,j,t,u,v;
char c[2],s[5],dumb;
scanf("%d\n",&t);
while(t--)
{
gets(c);
n=c[0]-64;
while(gets(s)){
if(s[0]=='\0')
break;
u=s[0]-65;
v=s[1]-65;
add(u,v);
}
int cnt=0;
memset(visited,0,sizeof visited);
for(i=0;i<n;i++){
if(!visited[i])
{
dfs(i);
cnt++;
}
}
if(t==0)
cout<<cnt<<endl;
else
cout<<cnt<<endl<<endl;
for(i=0;i<n;i++)
adj[i].clear();
}
}