首页 > 编程知识 正文

连通图最少几条边,无向图G有18条边

时间:2023-05-06 05:39:27 阅读:151735 作者:889

列举n个点、m条边的无向图,至少在此基础上增加多少条无向边,使任意两点都能到达~

输入说明:

第一行有两个正整数n和m。

在接下来的m行中,每行有两个正整数I,j,表示在点I和点j之间有向道路。

输出说明:

输出表示答案的整数

例1

输入

4 2

1 2

3 4

输出功率

1

备注:

对于100%的数据,有n,m=100000。

#includecstdioint n,m,I,x,y,ans,f[1000000]; intf(intx ) {return f[x]==x? x:f[x]=f(f[x]; (}int main ) ) Scanf('%d%d”,n,m ); for(I=1; i=n; I ) f(I )=I; ans=n-1; wile(m-- ) scanf ) ' %d%d ),x,y ); if(f ) x!=f(y ) ) ans--,f[f[x] )=f(y ); }printf('%d”,ans ); 返回0; }

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。