本文主要是介绍hdu 4635 Strongly connected（连通分量），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
/**在原有的有向连通图中插入尽可能多的边使其不是强连通 由于原图非强连通，因此至少存在一个强连通分支入度或出度为0。而且最后答案中的图中也应该存在这样的分支。通过添加边无法减少度，因此需要从度为0的分支中找出点数最少的并使其与外部的点相连且保留原属性
**/
typedef __int64 LL;
const int MAXN = 100005;
int n, m;
int head[MAXN], en;
int dfn[MAXN], low[MAXN], cnt;
int isin[MAXN], mstk[MAXN], top;
int cfz[MAXN], nfz, fz[MAXN];
int id[MAXN], od[MAXN];
struct edge
{int v, next;
}e[MAXN];
void add(int u, int v)
{e[en].v = v; e[en].next = head[u]; head[u] = en++;
}void solve(int u)
{dfn[u] = low[u] = ++cnt;isin[u] = 1;mstk[++top] = u;for (int i = head[u]; ~i; i = e[i].next){int v = e[i].v;if (!dfn[v]){solve(v);low[u] = min(low[v], low[u]);}else if (isin[v]){low[u] = min(low[u], dfn[v]);}}if (dfn[u] == low[u]){while (1){int v = mstk[top];isin[v] = 0;cfz[nfz]++, --top;fz[v] = nfz;if (u == v) break;}nfz++;}
}
void minit()
{memset(head, -1, sizeof head);en = 0;memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low);cnt = 0;memset(isin, 0, sizeof isin); top = 0;nfz = 0;memset(cfz, 0, sizeof cfz); memset(id, 0, sizeof id); memset(od, 0, sizeof od);
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endifint t, cs = 0;scanf("%d", &t);while (t--){printf("Case %d: ", ++cs);scanf("%d%d", &n, &m);minit();for (int i = 0; i< m; ++i){int u, v;scanf("%d%d", &u, &v);add(u, v);}for (int i= 1; i<= n; ++i){if (!dfn[i]) solve(i);}if (nfz == 1){printf("-1\n"); continue;}for (int u = 1; u<= n; ++u){for (int i = head[u]; ~i; i = e[i].next){int v = e[i].v;if (fz[u] != fz[v]){od[fz[u]]++; id[fz[v]]++;}}}LL sum = -1;for (int i = 0; i< nfz; ++i){LL x = cfz[i], y = n-cfz[i];if (id[i] == 0 || od[i] == 0){sum = max(sum, x*(x-1) + y*(y-1) + x*(n-x) - m);}}printf("%I64d\n", sum);}return 0;
}这篇关于hdu 4635 Strongly connected（连通分量）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
