HDU 3849 By Recognizing These Guys, We Find Social Networks Useful(双连通)
HDU 3849 By Recognizing These Guys, We Find Social Networks Useful
题意:说白了就是求一个无向图的桥
思路:字符串hash掉,然后双连通,要注意特判一下如果不是一个连通块,那么答案是0
代码:
#include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> using namespace std; const int N = 10005; const int M = 200005; int t, n, m; map<string, int> hash; char A[20], B[20]; struct Edge { int u, v, id; bool iscut; Edge() {} Edge(int u, int v, int id) { this->u = u; this->v = v; this->id = id; this->iscut = false; } } edge[M]; int en, first[N], next[M], hn; char name[N][20]; void init() { en = hn = 0; memset(first, -1, sizeof(first)); hash.clear(); } int get(char *str) { if (!hash.count(str)) { strcpy(name[hn], str); hash[str] = hn++; } return hash[str]; } void add_edge(int u, int v, int id) { edge[en] = Edge(u, v, id); next[en] = first[u]; first[u] = en++; } int pre[N], dfn[N], dfs_clock, ans = 0; void dfs_cut(int u, int f) { pre[u] = dfn[u] = ++dfs_clock; for (int i = first[u]; i + 1; i = next[i]) { if (edge[i].id == f) continue; int v = edge[i].v; if (!pre[v]) { dfs_cut(v, edge[i].id); dfn[u] = min(dfn[u], dfn[v]); if (dfn[v] > pre[u]) { ans++; edge[i].iscut = edge[i^1].iscut = true; } } else dfn[u] = min(dfn[u], pre[v]); } } void find_cut() { memset(pre, 0, sizeof(pre)); for (int i = 0; i < n; i++) if (!pre[i]) dfs_cut(i, -1); } int parent[N]; int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } int main() { scanf("%d", &t); while (t--) { init(); scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) parent[i] = i; int cnt = n; for (int i = 0; i < m; i++) { scanf("%s%s", A, B); int u = get(A), v = get(B); add_edge(u, v, i); add_edge(v, u, i); int pu = find(u), pv = find(v); if (pu != pv) { cnt--; parent[pu] = pv; } } if (cnt > 1) { printf("0\n"); continue; } ans = 0; find_cut(); printf("%d\n", ans); for (int i = 0; i < en; i += 2) if (edge[i].iscut) printf("%s %s\n", name[edge[i].u], name[edge[i].v]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。