专题九 连通图
√ POJ 1236 Network of Schools
√ UVA 315 Network
√ UVA 796 Critical Links
√ POJ 3694 Network
√ POJ 3177 Redundant Paths
√ HDU 4612 Warm up
√ HDU 4635 Strongly connected
√ HDU 4685 Prince and Princess
√ HDU 4738 Caocao's Bridges
// poj 1236
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN = 100+5; 5 const int MAXM = MAXN*MAXN; 6 7 int num; 8 int head[MAXN]; 9 struct node { 10 int v, next; 11 } edge[MAXM]; 12 13 inline void add(int x, int y) { 14 edge[num].v = y; 15 edge[num].next = head[x]; 16 head[x] = num++; 17 } 18 19 int cnt, t, scc_cnt; 20 int dfn[MAXN], low[MAXN], vis[MAXN], sccno[MAXN], stack[MAXN]; 21 void Tarjan(int cur) { 22 dfn[cur] = low[cur] = ++cnt; 23 vis[cur] = 1; 24 stack[t++] = cur; 25 for(int i = head[cur]; i != -1; i = edge[i].next) { 26 if(!dfn[edge[i].v]) { 27 Tarjan(edge[i].v); 28 low[cur] = min(low[cur], low[edge[i].v]); 29 } 30 else if(vis[edge[i].v]) { 31 low[cur] = min(low[cur], dfn[edge[i].v]); 32 } 33 } 34 if(dfn[cur] == low[cur]) { 35 ++scc_cnt; 36 int v; 37 do { 38 v = stack[--t]; 39 sccno[v] = scc_cnt; 40 vis[v] = 0; 41 } while(v != cur); 42 } 43 } 44 45 int n; 46 int in[MAXN], out[MAXN]; 47 48 int main() { 49 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 50 cin >> n; 51 num = 0; 52 for(int i = 1; i <= n; ++i) head[i] = -1; 53 int v; 54 for(int u = 1; u <= n; ++u) { 55 while(cin >> v && v) { 56 add(u, v); 57 } 58 } 59 cnt = t = scc_cnt = 0; 60 for(int i = 1; i <= n; ++i) { 61 if(!dfn[i]) Tarjan(i); 62 } 63 for(int i = 1; i <= n; ++i) { 64 for(int j = head[i]; j != -1; j = edge[j].next) { 65 if(sccno[i] != sccno[edge[j].v]) { 66 ++out[sccno[i]]; ++in[sccno[edge[j].v]]; 67 } 68 } 69 } 70 int inn = 0, outn = 0; 71 for(int i = 1; i <= scc_cnt; ++i) { 72 if(!in[i]) ++inn; 73 if(!out[i]) ++outn; 74 } 75 if(scc_cnt == 1) cout << "1 0 "; 76 else cout << inn << " " << max(inn, outn) << " "; 77 return 0; 78 }
// UVA 315
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-10-30 23:24:12 7 * @LastEditTime: 2019-10-31 00:22:49 8 */ 9 #include<cstdio> 10 #include<cstring> 11 #include<cmath> 12 #include<fstream> 13 #include<iostream> 14 #include<string> 15 #include<functional> 16 #include<algorithm> 17 #include<sstream> 18 #include<iomanip> 19 #include<vector> 20 #include<queue> 21 #include<stack> 22 #include<set> 23 #include<map> 24 #define read(n) n = read_n() 25 #define rep(i, n) for(int i=0;i!=n;++i) 26 #define per(i, n) for(int i=n-1;i>=0;--i) 27 #define Rep(i, sta, n) for(int i=sta;i!=n;++i) 28 #define rep1(i, n) for(int i=1;i<=n;++i) 29 #define per1(i, n) for(int i=n;i>=1;--i) 30 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i) 31 #define L k<<1 32 #define R k<<1|1 33 #define mid (tree[k].l+tree[k].r)>>1 34 #define eps 1e-10 35 using namespace std; 36 const int INF = 0x3f3f3f3f; 37 typedef long long ll; 38 39 inline int read_n() { 40 char c=getchar();int x=0,f=1; 41 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 42 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 43 return x*f; 44 } 45 // ----------------------------------------------------- 46 const int MAXN = 100+5; 47 const int MAXM = MAXN*MAXN; 48 49 int num; 50 int head[MAXN]; 51 struct node { 52 int v, next; 53 } edge[MAXM]; 54 55 inline void add(int x, int y) { 56 edge[num].v = y; 57 edge[num].next = head[x]; 58 head[x] = num++; 59 } 60 61 int n; 62 int cnt; 63 int dfn[MAXN], low[MAXN]; 64 set<int> disct; 65 66 void Tarjan(int cur, int root) { 67 dfn[cur] = low[cur] = ++cnt; 68 int flag = 0; 69 for(int i = head[cur]; i != -1; i = edge[i].next) { 70 int v = edge[i].v; 71 if(!dfn[v]) { 72 Tarjan(v, root); 73 low[cur] = min(low[cur], low[v]); 74 if(low[v] >= dfn[cur]) { 75 ++flag; 76 if(cur != root || flag > 1) disct.insert(cur); 77 } 78 } 79 else low[cur] = min(low[cur], dfn[v]); 80 } 81 } 82 83 void solve() { 84 cnt = 0; 85 disct.clear(); 86 rep1(i, n) dfn[i] = low[i] = 0; 87 rep1(i, n) if(!dfn[i]) Tarjan(i, i); 88 cout << disct.size() << " "; 89 } 90 91 int main() { 92 while(cin >> n && n) { 93 num = 0; 94 rep1(i, n) head[i] = -1; 95 int u, v; 96 while(cin >> u && u) { 97 while(getchar() != ' ') { 98 cin >> v; 99 add(u, v); add(v, u); 100 } 101 } 102 solve(); 103 } 104 return 0; 105 }
// UVA 796
1 All 2 Mine 3 Followed 4 Previous12345…NextFilterReset 5 Username 6 7 OJ 8 Prob 9 10 796 11 Result 12 Time 13 (ms) Mem 14 (MB) Lang 15 Submit Time 16 Arnoiii 17 UVA 18 796 19 Accepted 20 0 21 C++ 22 14 min ago 23 445514922 24 UVA 25 796 26 Accepted 27 0 28 C++ 29 10 hr ago 30 445514922 31 UVA 32 796 33 Accepted 34 0 35 C++ 36 10 hr ago 37 445514922 38 UVA 39 796 40 Accepted 41 0 42 C++ 43 10 hr ago 44 445514922 45 UVA 46 796 47 Wrong answer 48 C++ 49 10 hr ago 50 445514922 51 UVA 52 796 53 Wrong answer 54 C++ 55 10 hr ago 56 445514922 57 UVA 58 796 59 Wrong answer 60 C++ 61 10 hr ago 62 445514922 63 UVA 64 796 65 Wrong answer 66 C++ 67 10 hr ago 68 ori_arevalos 69 UVA 70 796 71 Wrong answer 72 Python 73 2 days ago 74 ori_arevalos 75 UVA 76 796 77 Wrong answer 78 Python 79 2 days ago 80 ori_arevalos 81 UVA 82 796 83 Wrong answer 84 Python 85 2 days ago 86 zyq2652192993 87 UVA 88 796 89 Accepted 90 0 91 C++ 92 2 days ago 93 zyq2652192993 94 UVA 95 796 96 Wrong answer 97 C++ 98 2 days ago 99 zyq2652192993 100 UVA 101 796 102 Wrong answer 103 C++ 104 2 days ago 105 zyq2652192993 106 UVA 107 796 108 Compilation error 109 C++ 110 2 days ago 111 zyq2652192993 112 UVA 113 796 114 Compilation error 115 C++ 116 2 days ago 117 Ada_Boost 118 UVA 119 796 120 Accepted 121 0 122 C++ 123 3 days ago 124 A19180294 125 UVA 126 796 127 Accepted 128 0 129 C++ 130 7 days ago 131 A19180294 132 UVA 133 796 134 Compilation error 135 C++ 136 7 days ago 137 A19180294 138 UVA 139 796 140 Accepted 141 0 142 C++ 143 7 days ago 144 145 All Copyright Reserved © 2010-2019 Xu Han 146 Server Time: 2019-10-31 02:44:32 CST 147 148 #22576444 | Arnoiii's solution for [UVA-796] 149 Status 150 Accepted 151 Length 152 1677 153 Lang 154 C++11 5.3.0 155 Submitted 156 2019-10-31 02:29:43 157 Shared 158 159 RemoteRunId 160 24127850 161 Select Code 162 /* 163 * @Promlem: 164 * @Time Limit: ms 165 * @Memory Limit: k 166 * @Author: pupil-XJ 167 * @Date: 2019-10-31 01:44:42 168 * @LastEditTime: 2019-10-31 02:23:39 169 */ 170 #include<cstdio> 171 #include<algorithm> 172 #include<vector> 173 #define rep(i, n) for(int i=0;i!=n;++i) 174 #define rep1(i, n) for(int i=1;i<=n;++i) 175 using namespace std; 176 const int MAXN = 1000+5; 177 const int MAXM = MAXN*MAXN; 178 typedef pair<int,int> Pair; 179 180 int num; 181 int head[MAXN]; 182 struct node { 183 int v, next; 184 } edge[MAXM]; 185 186 inline void add(int x, int y) { 187 edge[num].v = y; 188 edge[num].next = head[x]; 189 head[x] = num++; 190 } 191 192 int cnt; 193 int dfn[MAXN], low[MAXN], pre[MAXN]; 194 void Tarjan(int cur, int fa) { 195 dfn[cur] = low[cur] = ++cnt; 196 pre[cur] = fa; 197 bool flag = false; 198 for(int i = head[cur]; i != -1; i = edge[i].next) { 199 int v = edge[i].v; 200 if(v == fa && !flag) { 201 flag = true; 202 continue; 203 } 204 if(!dfn[v]) { 205 Tarjan(v, cur); 206 low[cur] = min(low[cur], low[v]); 207 } 208 else if(v != fa) low[cur] = min(low[cur], dfn[v]); 209 } 210 } 211 212 int n; 213 vector<Pair> ans; 214 215 void solve() { 216 cnt = 0; 217 ans.clear(); 218 rep(i, n) pre[i] = -1, dfn[i] = 0; 219 rep(i, n) if(!dfn[i]) Tarjan(i, -1); 220 rep(v, n) { 221 int u = pre[v]; 222 if(u != -1 && dfn[u] < low[v]) { 223 if(u < v) ans.push_back(make_pair(u, v)); 224 else ans.push_back(make_pair(v, u)); 225 } 226 } 227 sort(ans.begin(), ans.end()); 228 printf("%d critical links ",ans.size()); 229 rep(i, ans.size()) { 230 printf("%d - %d ",ans[i].first,ans[i].second); 231 } 232 printf(" "); 233 } 234 235 int main() { 236 while(scanf("%d", &n) == 1) { 237 num = 0; 238 rep(i, n) head[i] = -1; 239 int u, v, nm; 240 rep(i, n) { 241 scanf("%d (%d)", &u, &nm); 242 rep(j, nm) { 243 scanf("%d", &v); 244 if(u < v) add(u, v), add(v, u); 245 } 246 } 247 solve(); 248 } 249 return 0; 250 }
// poj 3694
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-10-31 10:02:18 7 * @LastEditTime: 2019-10-31 12:51:20 8 */ 9 #include<cstdio> 10 #include<algorithm> 11 #include<map> 12 #define rep(i, n) for(int i=0;i!=n;++i) 13 #define rep1(i, n) for(int i=1;i<=n;++i) 14 using namespace std; 15 16 inline int read() { 17 char c=getchar();int x=0,f=1; 18 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 19 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 20 return x*f; 21 } 22 // -------------------------------------------- 23 const int MAXN = 100000+5; 24 const int MAXM = 402000+5; 25 26 int num; 27 int head[MAXN]; 28 struct node { 29 int v, next; 30 } edge[MAXM]; 31 32 inline void add(int x, int y) { 33 edge[num].v = y; 34 edge[num].next = head[x]; 35 head[x] = num++; 36 } 37 38 int n, m, q; 39 int cnt, ans; 40 int dfn[MAXN], low[MAXN], pre[MAXN], deep[MAXN]; 41 bool bridge[MAXN]; 42 43 void Tarjan(int cur, int fa) { 44 dfn[cur] = low[cur] = ++cnt; 45 for(int i = head[cur]; i != -1; i = edge[i].next) { 46 int v = edge[i].v; 47 if(!dfn[v]) { 48 deep[v] = deep[cur] + 1; 49 pre[v] = cur; 50 Tarjan(v, cur); 51 low[cur] = min(low[cur], low[v]); 52 if(low[v] > dfn[cur]) bridge[v] = true, ++ans; 53 } 54 else if(v != fa) low[cur] = min(low[cur], dfn[v]); 55 } 56 } 57 58 int LCA(int x, int y) { 59 if(deep[x] < deep[y]) swap(x, y); 60 while(deep[x] != deep[y]) { 61 if(bridge[x]) --ans, bridge[x] = false; 62 x = pre[x]; 63 } 64 while(x != y) { 65 if(bridge[x]) --ans, bridge[x] = false; 66 if(bridge[y]) --ans, bridge[y] = false; 67 x = pre[x]; y = pre[y]; 68 } 69 return ans; 70 } 71 72 void solve(int qaq) { 73 cnt = ans = 0; 74 rep1(i, n) bridge[i] = false; 75 rep1(i, n) dfn[i] = 0; 76 deep[1] = 1; 77 Tarjan(1, 0); 78 printf("Case %d: ", qaq); 79 q = read(); 80 int x, y; 81 rep(i, q) { 82 x = read(); y = read(); 83 printf("%d ", LCA(x, y)); 84 } 85 printf(" "); 86 } 87 88 int main() { 89 int qaq = 1; 90 while(scanf("%d%d", &n, &m) == 2 && n) { 91 num = 0; 92 rep1(i, n) head[i] = -1; 93 int x, y; 94 rep(i, m) { 95 x = read(); y = read(); 96 add(x, y); add(y, x); 97 } 98 solve(qaq++); 99 } 100 return 0; 101 }
// poj 3177
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-10-31 17:35:38 7 * @LastEditTime: 2019-10-31 23:03:56 8 */ 9 #include<cstdio> 10 #include<cstring> 11 #include<cmath> 12 #include<fstream> 13 #include<iostream> 14 #include<string> 15 #include<functional> 16 #include<algorithm> 17 #include<sstream> 18 #include<iomanip> 19 #include<vector> 20 #include<queue> 21 #include<stack> 22 #include<set> 23 #include<map> 24 #define read(n) n = read_n() 25 #define rep(i, n) for(int i=0;i!=n;++i) 26 #define per(i, n) for(int i=n-1;i>=0;--i) 27 #define Rep(i, sta, n) for(int i=sta;i!=n;++i) 28 #define rep1(i, n) for(int i=1;i<=n;++i) 29 #define per1(i, n) for(int i=n;i>=1;--i) 30 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i) 31 #define L k<<1 32 #define R k<<1|1 33 #define mid (tree[k].l+tree[k].r)>>1 34 #define eps 1e-10 35 using namespace std; 36 const int INF = 0x3f3f3f3f; 37 typedef long long ll; 38 39 inline int read_n() { 40 char c=getchar();int x=0,f=1; 41 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 42 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 43 return x*f; 44 } 45 // ----------------------------------------------------- 46 const int MAXN = 5000+5; 47 const int MAXM = 20000+5; 48 49 int num; 50 int head[MAXN]; 51 struct node { 52 int v, next; 53 } edge[MAXM]; 54 55 inline void add(int x, int y) { 56 edge[num].v = y; 57 edge[num].next = head[x]; 58 head[x] = num++; 59 } 60 61 int n, m; 62 63 int cnt, scc_cnt, t; 64 int dfn[MAXN], low[MAXN], vis[MAXN], st[MAXN], sccno[MAXN]; 65 66 void Tarjan(int cur, int edge_num) { 67 dfn[cur] = low[cur] = ++cnt; 68 vis[cur] = 1; 69 st[t++] = cur; 70 for(int i = head[cur]; i != -1; i = edge[i].next) { 71 if(edge_num != -1 && i == (edge_num^1)) continue; 72 int v = edge[i].v; 73 if(!dfn[v]) { 74 Tarjan(v, i); 75 low[cur] = min(low[cur], low[v]); 76 } 77 else if(vis[v]) low[cur] = min(low[cur], dfn[v]); 78 } 79 if(dfn[cur] == low[cur]) { 80 ++scc_cnt; 81 int v; 82 do { 83 v = st[--t]; 84 sccno[v] = scc_cnt; 85 vis[v] = 0; 86 } while(v != cur); 87 } 88 } 89 90 set<int> edg[MAXN]; 91 void solve() { 92 cnt = scc_cnt = t = 0; 93 rep1(i, n) dfn[i] = vis[i] = 0, edg[i].clear(); 94 Tarjan(1, -1); 95 rep1(i, n) { 96 for(int j = head[i]; j != -1; j = edge[j].next) { 97 int v = edge[j].v; 98 if(sccno[i] != sccno[v]) edg[sccno[i]].insert(sccno[v]), edg[sccno[v]].insert(sccno[i]); 99 } 100 } 101 int sum = 0; 102 rep1(i, scc_cnt) if(edg[i].size() == 1) ++sum; 103 cout << (sum+1)/2 << " "; 104 } 105 106 int main() { 107 //ofstream outputfile; 108 //outputfile.open();Output.txt 109 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 110 while(cin >> n >> m) { 111 num = 0; 112 rep1(i, n) head[i] = -1; 113 int x, y; 114 rep(i, m) { 115 cin >> x >> y; 116 add(x, y); add(y, x); 117 } 118 solve(); 119 } 120 121 //outputfile.close(); 122 return 0; 123 }
// poj 4612
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-10-31 23:41:06 7 * @LastEditTime: 2019-11-01 00:57:51 8 */ 9 #include<cstdio> 10 #include<iostream> 11 #include<algorithm> 12 #include<stack> 13 #define read(n) n = read_n() 14 #define rep(i, n) for(int i=0;i!=n;++i) 15 #define rep1(i, n) for(int i=1;i<=n;++i) 16 #pragma comment(linker, "/STACK:102400000,102400000") 17 using namespace std; 18 19 inline int read_n() { 20 char c=getchar();int x=0,f=1; 21 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 22 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 23 return x*f; 24 } 25 // ----------------------------------------------------- 26 const int MAXN = 200000+5; 27 const int MAXM = 2000000+5; 28 29 int num; 30 int head[MAXN]; 31 struct node { 32 int v, next; 33 } edge[MAXM]; 34 35 inline void add(int x, int y) { 36 edge[num].v = y; 37 edge[num].next = head[x]; 38 head[x] = num++; 39 } 40 41 int numt; 42 int headt[MAXN]; 43 struct t { 44 int v, next; 45 } tree[MAXM]; 46 47 inline void addt(int x, int y) { 48 tree[numt].v = y; 49 tree[numt].next = headt[x]; 50 headt[x] = numt++; 51 } 52 53 int n, m; 54 int cnt, scc; 55 int dfn[MAXN], low[MAXN], sccno[MAXN]; 56 bool vis[MAXN]; 57 stack<int> st; 58 59 void Tarjan(int cur, int edge_num) {// 无向图缩点 60 dfn[cur] = low[cur] = ++cnt; 61 vis[cur] = true; 62 st.push(cur); 63 for(int i = head[cur]; i != -1; i = edge[i].next) { 64 if(edge_num != -1 && i == (edge_num^1)) continue; 65 int v = edge[i].v; 66 if(!dfn[v]) { 67 Tarjan(v, i); 68 low[cur] = min(low[cur], low[v]); 69 } 70 else if(vis[v]) low[cur] = min(low[cur], dfn[v]); 71 } 72 if(dfn[cur] == low[cur]) { 73 ++scc; 74 int v; 75 do { 76 v = st.top(); 77 st.pop(); 78 vis[v] = false; 79 sccno[v] = scc; 80 } while(v != cur); 81 } 82 } 83 84 int ans;// 树的直径 85 int dis[MAXN]; 86 87 void build() {// 建树 88 numt = 0; 89 rep1(u, n) { 90 for(int i = head[u]; i != -1; i = edge[i].next) { 91 int v = edge[i].v; 92 if(sccno[u] != sccno[v]) { 93 addt(sccno[u], sccno[v]); 94 addt(sccno[v], sccno[u]); 95 } 96 } 97 } 98 } 99 100 void dp(int cur) {// 树形dp求树的直径 101 vis[cur] = true; 102 for(int i = headt[cur]; i != -1; i = tree[i].next) { 103 int v = tree[i].v; 104 if(vis[v]) continue; 105 dp(v); 106 ans = max(ans, dis[cur] + dis[v] + 1); 107 dis[cur] = max(dis[cur], dis[v] + 1); 108 } 109 } 110 111 void solve() { 112 cnt = scc = 0; 113 rep1(i, n) dfn[i] = 0, vis[i] = false, headt[i] = -1; 114 Tarjan(1, -1); 115 build(); 116 rep1(i, scc) vis[i] = false, dis[i] = 0; 117 ans = 0; 118 dp(1); 119 cout << scc-1-ans << " "; 120 } 121 122 int main() { 123 while(scanf("%d%d", &n, &m) == 2 && n) { 124 num = 0; 125 rep1(i, n) head[i] = -1; 126 int x, y; 127 rep(i, m) { 128 read(x); read(y); 129 add(x, y); add(y, x); 130 } 131 solve(); 132 } 133 return 0; 134 }
// hdu 4635
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-11-01 08:09:22 7 * @LastEditTime: 2019-11-01 23:53:27 8 */ 9 #include<cstdio> 10 #include<algorithm> 11 #define read(n) n = read_n() 12 #define rep(i, n) for(int i=0;i!=n;++i) 13 #define rep1(i, n) for(int i=1;i<=n;++i) 14 #define ll long long int 15 using namespace std; 16 17 inline int read_n() { 18 char c=getchar();int x=0,f=1; 19 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 20 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 21 return x*f; 22 } 23 // ----------------------------------------------------- 24 const int MAXN = 100000+5; 25 const int MAXM = 200000+5; 26 27 int num; 28 int head[MAXN]; 29 struct node { 30 int v, next; 31 } edge[MAXM]; 32 33 inline void add(int x, int y) { 34 edge[num].v = y; 35 edge[num].next = head[x]; 36 head[x] = num++; 37 } 38 39 int n,m; 40 int cnt, scc, t; 41 int dfn[MAXN], low[MAXN], sccno[MAXN], st[MAXN], scc_num[MAXN]; 42 bool vis[MAXN]; 43 44 void Tarjan(int cur) { 45 dfn[cur] = low[cur] = ++cnt; 46 st[t++] = cur; 47 vis[cur] = true; 48 for(int i = head[cur]; i != -1; i = edge[i].next) { 49 int v = edge[i].v; 50 if(!dfn[v]) { 51 Tarjan(v); 52 low[cur] = min(low[cur], low[v]); 53 } 54 else if(vis[v]) low[cur] = min(low[cur], dfn[v]); 55 } 56 if(dfn[cur] == low[cur]) { 57 ++scc; 58 int v; 59 do { 60 v = st[--t]; 61 vis[v] = false; 62 sccno[v] = scc; 63 ++scc_num[scc]; 64 } while(v != cur); 65 } 66 } 67 68 int in[MAXN], out[MAXN]; 69 70 void solve(int qaq) { 71 cnt = scc = t = 0; 72 rep1(i, n) dfn[i] = in[i] = out[i] = scc_num[i] = 0, vis[i] = false; 73 rep1(i, n) if(!dfn[i]) Tarjan(i); 74 ll ans; 75 if(scc == 1) ans = -1; 76 else { 77 rep1(u, n) { 78 for(int i = head[u]; i != -1; i = edge[i].next) { 79 int v = edge[i].v; 80 if(sccno[u] != sccno[v]) { 81 ++out[sccno[u]]; ++in[sccno[v]]; 82 } 83 } 84 } 85 ans = 0; 86 rep1(i, scc) { 87 if(!in[i] || !out[i]) { 88 ll a = scc_num[i]; 89 ll b = n - a; 90 ans = max(ans, n*n-a*b-n-m); 91 } 92 } 93 } 94 printf("Case %d: %d ", qaq, ans); 95 } 96 97 int main() { 98 int T, qaq = 1; 99 scanf("%d", &T); 100 while(T--) { 101 read(n); read(m); 102 num = 0; 103 rep1(i, n) head[i] = -1; 104 int x, y; 105 rep(i, m) { 106 read(x); read(y); 107 add(x, y); 108 } 109 solve(qaq++); 110 } 111 return 0; 112 }
// hdu 4685
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-11-06 20:26:27 7 * @LastEditTime: 2019-11-08 10:37:11 8 */ 9 #include<cstdio> 10 #include<cstring> 11 #include<algorithm> 12 #include<set> 13 using namespace std; 14 15 inline int read() { 16 char c=getchar(); int f=1,x=0; 17 while(c<'0'||c>'9') { if(c=='-')f=-1;c=getchar(); } 18 while(c>='0'&&c<='9') { x=x*10+c-'0';c=getchar(); } 19 return f*x; 20 } 21 22 inline void write(int a) { 23 if(a<0)putchar('-'),a=-a; 24 if(a>9)write(a/10); 25 putchar(a%10+'0'); 26 } 27 //--------------------------------- 28 const int MAXN = 2000+5; 29 const int MAXE = 500*500; 30 31 int num; 32 int head[MAXN]; 33 struct node { 34 int v, next; 35 } edge[MAXE]; 36 37 inline void add(int x, int y) { 38 edge[num].v = y; 39 edge[num].next = head[x]; 40 head[x] = num++; 41 } 42 43 int n, m, sum; 44 int cx[MAXN], cy[MAXN]; 45 bool vis[MAXN]; 46 47 bool dfs(int u) { 48 vis[u] = true; 49 for(int i = head[u]; i != -1; i = edge[i].next) { 50 int v = edge[i].v; 51 if(!vis[v]) { 52 vis[v] = true; 53 if(!cy[v] || dfs(cy[v])) { 54 cx[u] = v; 55 cy[v] = u; 56 return true; 57 } 58 } 59 } 60 return false; 61 } 62 63 int hungry(int nm) { 64 int ans = 0; 65 for(int i = 1; i <= nm; ++i) cx[i] = cy[i] = 0; 66 for(int i = 1; i <= nm; ++i) { 67 for(int j = 1; j <= nm; ++j) vis[j] = false; 68 if(dfs(i)) ++ans; 69 } 70 return ans; 71 } 72 73 void build() { 74 sum = n+m; 75 int res = hungry(sum); 76 int xt = m-res, yt = n-res; 77 for(int i = 1; i <= xt; ++i) { 78 ++sum; 79 for(int j = n+1; j <= n+m; ++j) { 80 add(sum, j); 81 } 82 } 83 for(int i = 1; i <= yt; ++i) { 84 ++sum; 85 for(int j = 1; j <= n; ++j) { 86 add(j, sum); 87 } 88 } 89 hungry(sum); 90 for(int i = 1; i <= n+xt; ++i) add(cx[i], i); 91 for(int i = n+m+1; i <= n+m+xt; ++i) add(cx[i], i); 92 } 93 94 int cnt, scc_cnt, t; 95 int dfn[MAXN], low[MAXN], sccno[MAXN], st[MAXN]; 96 97 void Tarjan(int u) { 98 dfn[u] = low[u] = ++cnt; 99 st[++t] = u; 100 vis[u] = true; 101 for(int i = head[u]; i != -1; i = edge[i].next) { 102 int v = edge[i].v; 103 if(!dfn[v]) { 104 Tarjan(v); 105 low[u] = min(low[u], low[v]); 106 } 107 else if(vis[v]) low[u] = min(low[u], dfn[v]); 108 } 109 if(dfn[u] == low[u]) { 110 ++scc_cnt; 111 int v; 112 do { 113 v = st[t--]; 114 sccno[v] = scc_cnt; 115 vis[v] = false; 116 } while(v != u); 117 } 118 } 119 120 void solve() { 121 cnt = scc_cnt = t = 0; 122 for(int i = 1; i <= sum; ++i) dfn[i] = vis[i] = 0; 123 for(int i = 1; i <= sum; ++i) if(!dfn[i]) Tarjan(i); 124 for(int i = 1; i <= n; ++i) { 125 set<int> marry; 126 for(int j = head[i]; j != -1; j = edge[j].next) { 127 int v = edge[j].v; 128 if(v > n+m) continue; 129 if(sccno[i] == sccno[v]) marry.insert(v-n); 130 } 131 write(marry.size()); 132 for(set<int>::iterator j = marry.begin(); j != marry.end(); ++j) { 133 putchar(' '); 134 write(*j); 135 } 136 putchar(' '); 137 } 138 } 139 140 int main() { 141 int T = read(), Case = 0; 142 int nm, x; 143 while(T--) { 144 n = read(); m = read(); 145 num = 0; 146 memset(head, -1, sizeof(head)); 147 for(int i = 1; i <= n; ++i) { 148 nm = read(); 149 for(int j = 0; j != nm; ++j) { 150 x = read(); 151 add(i, x+n); 152 } 153 } 154 printf("Case #%d: ", ++Case); 155 build(); 156 solve(); 157 } 158 return 0; 159 }
// hdu 4738
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<set> 5 #include<map> 6 #define read(n) n = read_n() 7 #define rep(i, n) for(int i=0;i!=n;++i) 8 #define rep1(i, n) for(int i=1;i<=n;++i) 9 using namespace std; 10 11 inline int read_n() { 12 char c=getchar();int x=0,f=1; 13 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 14 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 15 return x*f; 16 } 17 // ----------------------------------------------------- 18 const int MAXN = 1000+5; 19 const int MAXM = MAXN*MAXN; 20 typedef pair<int,int> Pair; 21 22 int num; 23 int head[MAXN]; 24 struct node { 25 int v, next; 26 int w; 27 } edge[MAXM]; 28 29 inline void add(int x, int y, int w) { 30 edge[num].v = y; 31 edge[num].next = head[x]; 32 edge[num].w = w; 33 head[x] = num++; 34 } 35 36 int n, m; 37 int cnt; 38 int dfn[MAXN], low[MAXN]; 39 set<int> ct; 40 set<Pair> bb; 41 42 void Tarjan(int cur, int fa) { 43 dfn[cur] = low[cur] = ++cnt; 44 for(int i = head[cur]; i != -1; i = edge[i].next) { 45 int v = edge[i].v; 46 if(!dfn[v]) { 47 Tarjan(v, cur); 48 low[cur] = min(low[cur], low[v]); 49 if(low[v] > dfn[cur] && !bb.count(make_pair(cur, v)) && !bb.count(make_pair(v, cur))) ct.insert(edge[i].w); 50 } 51 else if(v != fa) low[cur] = min(low[cur], dfn[v]); 52 } 53 } 54 55 void solve() { 56 cnt = 0; 57 int flag = 0; 58 ct.clear(); 59 rep1(i, n) dfn[i] = 0; 60 rep1(i, n) if(!dfn[i]) ++flag, Tarjan(i, 0); 61 if(flag > 1) printf("0 "); 62 else if(ct.empty()) printf("-1 "); 63 else printf("%d ", *(ct.begin()) == 0 ? 1 : *(ct.begin())); 64 } 65 66 int main() { 67 while(scanf("%d%d", &n, &m) == 2 && n) { 68 num = 0; 69 rep1(i, n) head[i] = -1; 70 set<Pair> b; 71 bb.clear(); 72 int x, y, w; 73 rep(i, m) { 74 read(x); read(y); read(w); 75 if(x > y) swap(x, y); 76 Pair p = make_pair(x, y); 77 if(!b.count(p)) { 78 add(x, y, w); 79 add(y, x, w); 80 b.insert(p); 81 } 82 else bb.insert(p); 83 } 84 solve(); 85 } 86 return 0; 87 }