codeforces 217A Ice Skating

题意：加点，使图变成强连通图。

做法：直接求出强连通分量个数，ans=连通数-1；

#include <iostream>
#include<utility>
#include<vector>
#include<cstdio>
using namespace std;
bool gra[105][105];
int vis[105],sign[105],time[105],t,ans;
int n;
vector< pair<int,int> >node;
void dfs(int u)
{
vis[u]=1;
sign[u]=time[u]=++t;
int i;
for(i=0;i<n;i++)
if(gra[u][i])
{
if(0==vis[i])
{
dfs(i);
sign[u]=sign[u]<sign[i]?sign[u]:sign[i];
}
if(1==vis[i])
sign[u]=sign[u]<time[i]?sign[u]:time[i];
}
vis[u]=2;
if(time[u]==sign[u])ans++;
}
int main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
node.push_back(make_pair(x,y));
for(j=0;j<i;j++)
if(node[i].first==node[j].first||node[j].second==node[i].second)
gra[i][j]=gra[j][i]=1;
}
for(i=0;i<n;i++)
if(0==vis[i])dfs(i);
printf("%dn",--ans);
}

最后

以上就是高高大叔最近收集整理的关于codeforces 217A Ice Skating的全部内容，更多相关codeforces内容请搜索靠谱客的其他文章。