HRBUST 1311 火影忍者之~忍者村

求连通块。

$ABC$之间建好边,然后计算连通块的个数。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<iostream>
using namespace std; map<string,int>m;
char op1[],op2[],op3[];
int n,sz,ans,f[]; vector<int>G[]; void dfs(int x)
{
f[x]=;
for(int i=;i<G[x].size();i++)
{
if(f[G[x][i]]) continue;
dfs(G[x][i]);
}
} int main()
{
while(~scanf("%d",&n))
{
m.clear();
sz=; for(int i=;i<=;i++) G[i].clear();
for(int i=; i<=n; i++)
{
scanf("%s%s%s",op1,op2,op3);
int A,B,C;
if(m[op1]==) m[op1]=sz++;
if(m[op2]==) m[op2]=sz++;
if(m[op3]==) m[op3]=sz++; A=m[op1];
B=m[op2];
C=m[op3]; G[A].push_back(B);
G[B].push_back(A); G[A].push_back(C);
G[C].push_back(A); G[B].push_back(C);
G[C].push_back(B);
} memset(f,,sizeof f); ans=;
for(int i=;i<=sz-;i++)
{
if(f[i]) continue;
ans++;
dfs(i);
} printf("%d\n",ans);
}
return ;
}
上一篇:使pre的内容自动换行


下一篇:findbugs插件使用