强连通是真的强~

题目大意求有向连通图强连通分支入度为0的点和加几条边变成强连通图

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 100005
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26 }edge[MAXN];
 27 
 28 int in[MAXN];
 29 int out[MAXN];
 30 int low[MAXN];
 31 int dfn[MAXN];
 32 int vis[MAXN];
 33 int from[MAXN];
 34 int belong[MAXN];
 35 int cnt_1;
 36 int cnt_2;
 37 int cnt_3;
 38 stack<int> s1;
 39 int N;
 40 int mx1, mx2;
 41 
 42 void init(void) {
 43     memset(in, 0, sizeof(in));
 44     memset(out, 0, sizeof(out));
 45     memset(low, 0, sizeof(low));
 46     memset(dfn, 0, sizeof(dfn));
 47     memset(vis, 0, sizeof(vis));
 48     memset(from, 0, sizeof(from));
 49     memset(belong, 0, sizeof(belong));
 50     cnt_1 = 0;
 51     cnt_2 = 0;
 52     cnt_3 = 0;
 53     mx1 = 0;
 54     mx2 = 0;
 55     while (s1.size())
 56         s1.pop();
 57 }
 58 
 59 void add(int x, int y) {
 60     edge[++cnt_1].next = from[x];
 61     edge[cnt_1].to = y;
 62     from[x] = cnt_1;
 63 }
 64 
 65 void tarjan(int x) {
 66     s1.push(x);
 67     vis[x] = 1;
 68     dfn[x] = low[x] = ++cnt_2;
 69     for (int j = from[x]; j; j = edge[j].next) {
 70         int k = edge[j].to;
 71         if (!dfn[k]) {
 72             tarjan(k);
 73             low[x] = min(low[x], low[k]);
 74         }
 75         else if (vis[k] && dfn[k] < low[x])
 76             low[x] = dfn[k];
 77     }
 78     if (dfn[x] == low[x]) {
 79         int temp;
 80         cnt_3++;
 81         do{
 82             temp = s1.top();
 83             s1.pop();
 84             vis[temp] = 0;
 85             belong[temp] = cnt_3;
 86         } while (temp != x);
 87     }
 88     
 89     
 90 }
 91 
 92 void f1(void) {
 93 
 94     for (int i = 1; i <= N; i++) {
 95         for (int j = from[i]; j; j = edge[j].next) {
 96             int k = edge[j].to;
 97             if (belong[i] != belong[k]) {
 98                 ++in[belong[k]];
 99                 ++out[belong[i]];
100             }
101         }
102     }
103 
104     for (int i = 1; i <= cnt_3; i++) {
105         if (!in[i])
106             mx1++;
107         if (!out[i])
108             mx2++;
109     }
110 }
111 
112 int main()
113 {
114     //freopen("data.txt", "r", stdin);
115     int T;
116     while (~scanf("%d",&N)) {
117         init();
118         int a;
119         for (int i = 1; i <= N; i++) {
120             while (scanf("%d",&a)) {
121                 if (!a)
122                     break;
123                 add(i, a);
124             }
125             
126         }
127         for (int i = 1; i <= N; i++) {
128             if(!dfn[i])
129                 tarjan(i);
130         }
131         f1();
132         if (cnt_3 == 1)
133             printf("1
0
");
134         else {
135             /*cout << mx1 << endl;
136             cout << max(mx1, mx2) << endl;*/
137             printf("%d
%d
", mx1, max(mx1, mx2));
138         }
139     }
140     
141 
142     //freopen("CON", "r", stdin);
143     //system("pause");
144     return 0;
145 }

上代码

第二题

题目大意无向图求割点个数

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 105
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26 }edge[MAXN*MAXN];
 27 
 28 int is[MAXN];
 29 int in[MAXN];
 30 int out[MAXN];
 31 int low[MAXN];
 32 int dfn[MAXN];
 33 int vis[MAXN];
 34 int from[MAXN];
 35 int belong[MAXN];
 36 int parent[MAXN];
 37 int cnt_1;
 38 int cnt_2;
 39 int cnt_3;
 40 stack<int> s1;
 41 int N;
 42 int mx1, mx2;
 43 
 44 void init(void) {
 45     memset(is, 0, sizeof(is));
 46     memset(in, 0, sizeof(in));
 47     memset(out, 0, sizeof(out));
 48     memset(low, 0, sizeof(low));
 49     memset(dfn, 0, sizeof(dfn));
 50     memset(vis, 0, sizeof(vis));
 51     memset(from, 0, sizeof(from));
 52     memset(belong, 0, sizeof(belong));
 53     memset(parent, 0, sizeof(parent));
 54     cnt_1 = 0;
 55     cnt_2 = 0;
 56     cnt_3 = 0;
 57     mx1 = 0;
 58     mx2 = 0;
 59     while (s1.size())
 60         s1.pop();
 61 }
 62 
 63 void add(int x, int y) {
 64     edge[++cnt_1].next = from[x];
 65     edge[cnt_1].to = y;
 66     from[x] = cnt_1;
 67 }
 68 
 69 void tarjan(int x) {
 70     dfn[x] = low[x] = ++cnt_2;
 71     int children = 0;
 72     for (int i = from[x]; i; i = edge[i].next) {
 73         int k = edge[i].to;
 74         if (!dfn[k]) {
 75             parent[k] = x;
 76             children++;
 77             tarjan(k);
 78             low[x] = min(low[x], low[k]);
 79             if (!parent[x] && children > 1)
 80                 is[x] = 1;
 81             if (parent[x] && dfn[x] <= low[k])
 82                 is[x] = 1;
 83         }
 84         else if (parent[x] != k && low[x] > dfn[k])
 85             low[x] = dfn[k];
 86 
 87 
 88     }
 89 
 90 
 91 }
 92 
 93 int main()
 94 {
 95     //freopen("data.txt", "r", stdin);
 96     int T;
 97     while (cin >> T) {
 98         if (!T)
 99             break;
100         init();
101         string s1;
102         getchar();
103         while (1) {
104             getline(cin, s1);
105             if (s1 == "0")
106                 break;
107             istringstream ss1(s1);
108             int a;
109             int b;
110             ss1 >> a;
111             while (ss1 >> b) {
112                 add(a, b);
113                 add(b, a);
114             }
115         }
116         for (int i = 1; i <= T; i++) {
117             if (!dfn[i])
118                 tarjan(i);
119         }
120         int ans = 0;
121         for (int i = 1; i <= T; i++) {
122             if (is[i])
123                 ans++;
124         }
125         cout << ans << endl;
126     }
127 
128 
129     //freopen("CON", "r", stdin);
130     //system("pause");
131     return 0;
132 }
133 
134 很简单嘛

很简单嘛

第三题

题目大意无向图求桥

PS：坑题 0 0不是结尾搞了一上午~

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 1005
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26 }edge[MAXN*MAXN];
 27 
 28 int low[MAXN];
 29 int dfn[MAXN];
 30 int from[MAXN];
 31 int iscut[MAXN];
 32 int parent[MAXN];
 33 int cnt_1;
 34 int cnt_2;
 35 set<pair<int, int> > s1;
 36 int ans = 0;
 37 
 38 
 39 void init(void) {
 40     memset(low, 0, sizeof(low));
 41     memset(dfn, 0, sizeof(dfn));
 42     memset(from, 0, sizeof(from));
 43     memset(iscut, 0, sizeof(iscut));
 44     memset(parent, 0, sizeof(parent));
 45     cnt_1 = 0;
 46     cnt_2 = 0;
 47     s1.clear();
 48     ans = 0;
 49 }
 50 
 51 void add(int x, int y) {
 52     edge[++cnt_1].next = from[x];
 53     edge[cnt_1].to = y;
 54     from[x] = cnt_1;
 55 }
 56 
 57 void tarjan(int x) {
 58     dfn[x] = low[x] = ++cnt_2;
 59     for (int i = from[x]; i; i = edge[i].next) {
 60         int k = edge[i].to;
 61         if (!dfn[k]) {
 62             parent[k] = x;
 63             tarjan(k);
 64             low[x] = min(low[x], low[k]);
 65             if (dfn[x] < low[k]) {
 66 
 67                 s1.insert(make_pair(min(x, k), max(x, k)));
 68             }
 69         }
 70         else if (parent[x] != k && low[x] > dfn[k])
 71             low[x] = dfn[k];
 72     }
 73 }
 74 
 75 int main()
 76 {
 77     //freopen("data.txt", "r", stdin);
 78     int T;
 79     while (cin >> T) {
 80         init();
 81         for (int i = 1; i <= T; i++) {
 82             int a;
 83             cin >> a;
 84             a++;
 85             int len;
 86             int b;
 87             getchar();
 88             scanf("(%d)", &len);
 89             for (int i = 1; i <= len; i++) {
 90                 cin >> b;
 91                 if (a <= b + 1)
 92                     continue;
 93                 add(a, b + 1);
 94                 add(b + 1, a);
 95             }
 96         }
 97         for (int i = 1; i <= T; i++)
 98             if (!dfn[i])
 99                 tarjan(i);
100         //cout << s1.size();
101         printf("%d critical links
", s1.size());
102         for (set<pair<int, int> >::iterator it1 = s1.begin(); it1 != s1.end(); it1++)
103             cout << it1->first - 1 << " - " << it1->second - 1 << endl;
104         cout << endl;
105     }
106     //freopen("CON", "r", stdin);
107     //system("pause");
108     return 0;
109 }

再来一个

第四题

题目大意无向图给你边后判断加上后还有几条桥

PS：新知识 LCA 对我只是很简单的了解下LCA 各种写法为了不破坏基本结构挑选了一种 f3是LCA 你会神奇的发现注释掉第三个循环依然能AC 有些题是1和3循环注释掉第二个也AC

PS：此题解有bug emmmmm 对样例有bug 题目测试数据也有 bug 别看了处理不了重边后面代码可以处理重边因为写到这道题没有学会处理重边//以后我会改的

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 110000
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26 }edge[MAXN * 4];
 27 
 28 int low[MAXN];
 29 int dfn[MAXN];
 30 int from[MAXN];
 31 int iscut[MAXN];
 32 int parent[MAXN];
 33 int cnt_1;
 34 int cnt_2;
 35 int ans;
 36 
 37 void init(void) {
 38     memset(low, 0, sizeof(low));
 39     memset(dfn, 0, sizeof(dfn));
 40     memset(from, 0, sizeof(from));
 41     memset(iscut, 0, sizeof(iscut));
 42     memset(parent, 0, sizeof(parent));
 43     cnt_1 = 0;
 44     cnt_2 = 0;
 45     ans = 0;
 46 }
 47 
 48 void add(int x, int y) {
 49     edge[++cnt_1].next = from[x];
 50     edge[cnt_1].to = y;
 51     from[x] = cnt_1;
 52 }
 53 
 54 void tarjan(int x) {
 55     dfn[x] = low[x] = ++cnt_2;
 56     for (int i = from[x]; i; i = edge[i].next) {
 57         int k = edge[i].to;
 58         if (!dfn[k]) {
 59             parent[k] = x;
 60             tarjan(k);
 61             low[x] = min(low[x], low[k]);
 62             if (dfn[x] < low[k])
 63                 iscut[k] = 1, ans++;
 64         }
 65         else if (parent[x] != k && low[x] > dfn[k])
 66             low[x] = dfn[k];
 67     }
 68 }
 69 
 70 void f3(int a, int b) {
 71     if (dfn[a] < dfn[b])
 72         swap(a, b);
 73     while (dfn[a] > dfn[b])
 74     {
 75         if (iscut[a])
 76             ans--, iscut[a] = 0;
 77         a = parent[a];
 78     }
 79     while (dfn[b] > dfn[a])
 80     {
 81         if (iscut[b])
 82             ans--, iscut[b] = 0;
 83         b = parent[b];
 84     }
 85     /*while (a != b)
 86     {
 87         if (iscut[a])
 88             ans--, iscut[a] = 0;
 89         if (iscut[b])
 90             ans--, iscut[b] = 0;
 91         a = parent[a], b = parent[b];
 92     }*/
 93 }
 94 
 95 int main()
 96 {
 97     //freopen("data.txt", "r", stdin);
 98 
 99     int N, M;
100     int case1 = 1;
101     int a, b;
102     while (~scanf("%d%d", &N, &M)) {
103         if (!N && !M)
104             break;
105         init();
106         for (int i = 1; i <= M; i++) {
107             scanf("%d%d", &a, &b);
108             add(a, b);
109             add(b, a);
110         }
111         int K;
112         scanf("%d", &K);
113         /*if (case1 != 1)
114             printf("
");*/
115             //cout << "Case " << case1++ << ":" << endl;
116         printf("Case %d:
", case1++);
117         tarjan(1);
118         //f2(N);
119         while (K--) {
120 
121             scanf("%d%d", &a, &b);
122             f3(a, b);
123             //cout << ans << endl;
124             printf("%d
", ans);
125         }
126         printf("
");
127     }
128 
129     //freopen("CON", "r", stdin);
130     //system("pause");
131     return 0;
132 }

代码太难

第五题

题目大意无向图最少加几条边变成双连通

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 110000
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26 }edge[MAXN*4];
 27 
 28 int low[MAXN];
 29 int dfn[MAXN];
 30 int deg[MAXN];
 31 int from[MAXN];
 32 int iscut[MAXN];
 33 int parent[MAXN];
 34 int belong[MAXN];
 35 int instack[MAXN];
 36 int cnt_1;
 37 int cnt_2;
 38 int cnt_3;
 39 int ans;
 40 stack<int> s1;
 41 
 42 void init(void) {
 43     memset(low, 0, sizeof(low));
 44     memset(dfn, 0, sizeof(dfn));
 45     memset(deg, 0, sizeof(deg));
 46     memset(from, 0, sizeof(from));
 47     memset(iscut, 0, sizeof(iscut));
 48     memset(parent, 0, sizeof(parent));
 49     memset(belong, 0, sizeof(belong));
 50     memset(instack, 0, sizeof(instack));
 51     cnt_1 = 0;
 52     cnt_2 = 0;
 53     cnt_3 = 0;
 54     ans = 0;
 55     while (!s1.empty())
 56         s1.pop();
 57 }
 58 
 59 void add(int x, int y) {
 60     edge[++cnt_1].next = from[x];
 61     edge[cnt_1].to = y;
 62     from[x] = cnt_1;
 63 }
 64 
 65 void tarjan(int x) {
 66     s1.push(x);
 67     instack[x] = 1;
 68     dfn[x] = low[x] = ++cnt_2;
 69     
 70     for (int i = from[x]; i; i = edge[i].next) {
 71         int k = edge[i].to;
 72         if (iscut[k] == 1 && parent[k] == x) {//重边
 73             iscut[k] = 2;
 74         }
 75         if (!dfn[k]) {
 76             parent[k] = x;
 77             tarjan(k);
 78             low[x] = min(low[x], low[k]);
 79             if (dfn[x] < low[k])
 80                 iscut[k] = 1;
 81         }
 82         else if (parent[x] != k && instack[x])
 83             low[x] = min(low[x], dfn[k]);
 84         
 85     }
 86     if (dfn[x] == low[x]) {
 87         cnt_3++;
 88         int temp;
 89         do {
 90             temp = s1.top();
 91             s1.pop();
 92             belong[temp] = cnt_3;
 93             instack[temp] = 0;
 94         } while (temp != x);
 95     }
 96 }
 97 
 98 void solve(int N) {
 99     for (int i = 1; i <= N; i++)
100         if (!dfn[i])
101             tarjan(i);
102     for (int i = 1; i <= N; i++) {
103         for (int j = from[i]; j; j = edge[j].next) {
104             int k = edge[j].to;
105             if (iscut[k] == 1 && parent[k] == i) {
106                 deg[belong[i]]++;
107                 deg[belong[k]]++;
108             }
109         }
110     }
111     for (int i = 1; i <= cnt_3; i++)
112         if (deg[i] == 1)
113             ans++;
114 }
115 
116 void f3(int a, int b) {
117     if (dfn[a] < dfn[b])
118         swap(a, b);
119     while (dfn[a] > dfn[b])
120     {
121         if (iscut[a])
122             ans--, iscut[a] = 0;
123         a = parent[a];
124     }
125     while (dfn[b] > dfn[a])
126     {
127         if (iscut[b])
128             ans--, iscut[b] = 0;
129         b = parent[b];
130     }
131     while (a != b)
132     {
133         if (iscut[a])
134             ans--, iscut[a] = 0;
135         if (iscut[b])
136             ans--, iscut[b] = 0;
137         a = parent[a], b = parent[b];
138     }
139 }
140 
141 int main()
142 {
143     //freopen("data.txt", "r", stdin);
144 
145     int N, M;
146     while (cin >> N >> M) {
147         init();
148         for (int i = 1; i <= M; i++) {
149             int a, b;
150             scanf("%d%d", &a, &b);
151             add(a, b);
152             add(b, a);
153         }
154         solve(N);
155         printf("%d
", (ans + 1) / 2);
156     }
157     
158 
159     //freopen("CON", "r", stdin);
160     //system("pause");
161     return 0;
162 }

我要去当实习生

第六题

题目大意无向图你只能加一条边最少剩下几条桥

PS：新知识缩点+求树半径

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 210000
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26     int qz;
 27 }edge[(int)(4e6 + 100)];
 28 
 29 int low[MAXN];
 30 int dfn[MAXN];
 31 int deg[MAXN];
 32 int vis[MAXN];
 33 int from[MAXN];
 34 int iscut[MAXN];
 35 int qzcut[MAXN];
 36 int parent[MAXN];
 37 int belong[MAXN];
 38 int instack[MAXN];
 39 int cnt_1;
 40 int cnt_2;
 41 int cnt_3;
 42 int temp;
 43 int ans;
 44 stack<int> s1;
 45 
 46 void init(void) {
 47     memset(low, 0, sizeof(low));
 48     memset(dfn, 0, sizeof(dfn));
 49     memset(deg, 0, sizeof(deg));
 50     memset(vis, 0, sizeof(vis));
 51     memset(from, 0, sizeof(from));
 52     memset(iscut, 0, sizeof(iscut));
 53     memset(qzcut, 0x3f, sizeof(qzcut));
 54     memset(parent, 0, sizeof(parent));
 55     memset(belong, 0, sizeof(belong));
 56     memset(instack, 0, sizeof(instack));
 57     cnt_1 = 0;
 58     cnt_2 = 0;
 59     cnt_3 = 0;
 60     ans = 0;
 61     temp = 0;
 62     while (!s1.empty())
 63         s1.pop();
 64 }
 65 
 66 void init_2(void) {
 67     memset(vis, 0, sizeof(vis));
 68     memset(from, 0, sizeof(from));
 69     cnt_1 = 0;
 70     cnt_2 = 0;
 71 }
 72 
 73 void add(int x, int y) {
 74     edge[++cnt_1].next = from[x];
 75     edge[cnt_1].to = y;
 76     from[x] = cnt_1;
 77 }
 78 
 79 void tarjan(int x) {
 80     s1.push(x);
 81     instack[x] = 1;
 82     dfn[x] = low[x] = ++cnt_2;
 83     int flag = 0;
 84     for (int i = from[x]; i; i = edge[i].next) {
 85 
 86         int k = edge[i].to;
 87         if (!flag&&k == parent[x]) {
 88             flag = 1;
 89             continue;
 90         }
 91         /*if (iscut[k] == 1 && parent[k] == x) {//重边
 92             iscut[k] = 2;
 93         }*/
 94         if (!dfn[k]) {
 95             parent[k] = x;
 96             tarjan(k);
 97             low[x] = min(low[x], low[k]);
 98             if (dfn[x] < low[k]) {
 99                 iscut[k] = 1;
100                 qzcut[k] = min(qzcut[k], edge[i].qz);
101             }
102         }
103         else if (instack[k])
104             low[x] = min(low[x], dfn[k]);
105 
106     }
107     if (dfn[x] == low[x]) {
108         cnt_3++;
109         int temp;
110         do {
111             temp = s1.top();
112             s1.pop();
113             belong[temp] = cnt_3;
114             instack[temp] = 0;
115         } while (temp != x);
116     }
117 }
118 
119 void dfs(int x, int dist) {
120     vis[x] = dist;
121     if (vis[x] > ans) {
122         temp = x;
123         ans = vis[x];
124     }
125     for (int j = from[x]; j; j = edge[j].next) {
126         int k = edge[j].to;
127         if (!vis[k])
128             dfs(k, dist + 1);
129     }
130 }
131 
132 void solve(int N) {
133     int max = 0;
134     for (int i = 1; i <= N; i++)
135         if (!dfn[i])
136             tarjan(i);
137     init_2();
138     for (int i = 1; i <= N; i++) {
139         if (iscut[i] == 1) {
140             max++;
141             add(belong[parent[i]], belong[i]);
142             add(belong[i], belong[parent[i]]);
143         }
144     }
145     temp = 0;
146     ans = 0;
147     dfs(1, 1);
148     ans = 0;
149     memset(vis, 0, sizeof(vis));
150     dfs(temp, 1);
151     printf("%d
", max - ans + 1);
152 }
153 
154 int main()
155 {
156     //freopen("data.txt", "r", stdin);
157 
158     int N, M;
159     while (cin >> N >> M) {
160         if (!N && !M)
161             break;
162         init();
163         for (int i = 1; i <= M; i++) {
164             int a, b;
165             scanf("%d%d", &a, &b);
166             add(a, b);
167             add(b, a);
168         }
169         solve(N);
170 
171     }
172 
173 
174     //freopen("CON", "r", stdin);
175     //system("pause");
176     return 0;
177 }

回到正题

第七题

题目大意无向图最多加几条边仍然不是双连通

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 210000
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26 }edge[(int)(4e6+100)];
 27 
 28 int in[MAXN];
 29 int out[MAXN];
 30 int sum[MAXN];
 31 int low[MAXN];
 32 int dfn[MAXN];
 33 int deg[MAXN];
 34 int vis[MAXN];
 35 int from[MAXN];
 36 int iscut[MAXN];
 37 int qzcut[MAXN];
 38 int parent[MAXN];
 39 int belong[MAXN];
 40 int instack[MAXN];
 41 int cnt_1;
 42 int cnt_2;
 43 int cnt_3;
 44 int temp;
 45 int minn;
 46 int ans;
 47 stack<int> s1;
 48 int N, M;
 49 
 50 void init(void) {
 51     memset(in, 0, sizeof(in));
 52     memset(out, 0, sizeof(out));
 53     memset(sum, 0, sizeof(sum));
 54     memset(low, 0, sizeof(low));
 55     memset(dfn, 0, sizeof(dfn));
 56     memset(deg, 0, sizeof(deg));
 57     memset(vis, 0, sizeof(vis));
 58     memset(from, 0, sizeof(from));
 59     memset(iscut, 0, sizeof(iscut));
 60     memset(qzcut, 0x3f, sizeof(qzcut));
 61     memset(parent, 0, sizeof(parent));
 62     memset(belong, 0, sizeof(belong));
 63     memset(instack, 0, sizeof(instack));
 64     cnt_1 = 0;
 65     cnt_2 = 0;
 66     cnt_3 = 0;
 67     ans = 0;
 68     temp = 0;
 69     minn = INF;
 70     while (!s1.empty())
 71         s1.pop();
 72 }
 73 
 74 void init_2(void){
 75     memset(vis, 0, sizeof(vis));
 76     memset(from, 0, sizeof(from));
 77     cnt_1 = 0;
 78     cnt_2 = 0;
 79     ans = 0;
 80 }
 81 
 82 void add(int x, int y) {
 83     edge[++cnt_1].next = from[x];
 84     edge[cnt_1].to = y;
 85     from[x] = cnt_1;
 86 }
 87 
 88 void tarjan(int x) {
 89     dfn[x] = low[x] = ++cnt_2;
 90     vis[x] = 1;
 91     s1.push(x);
 92     for (int i = from[x]; i; i = edge[i].next) {
 93         int v = edge[i].to;
 94         if (!dfn[v]) {
 95             tarjan(v);
 96             low[x] = min(low[x], low[v]);
 97         }
 98         else if (vis[v]) low[x] = min(low[x], dfn[v]);
 99     }
100     if (dfn[x] == low[x]) {
101         cnt_3++;
102         int k;
103         do {
104             k = s1.top();
105             s1.pop();
106             vis[k] = 0;
107             belong[k] = cnt_3;
108             sum[cnt_3]++;
109         } while (k != x);
110     }
111 }
112 
113 void dfs(int x,int dist) {
114     vis[x] = dist;
115     if (vis[x] > ans) {
116         temp = x;
117         ans = vis[x];
118     }
119     for (int j = from[x]; j; j = edge[j].next) {
120         int k = edge[j].to;
121         if (!vis[k])
122             dfs(k, dist + 1);
123     }
124 }
125 
126 void solve(void) {
127     for (int i = 1; i <= N; i++)
128         if (!dfn[i])
129             tarjan(i);
130     if (cnt_3 == 1) {
131         cout << -1 << endl;
132         return;
133     }
134     else {
135         for (int i = 1; i <= N; i++) {
136             for (int j = from[i]; j; j = edge[j].next) {
137                 int k = edge[j].to;
138                 if (belong[i] != belong[k]) {
139                     out[belong[i]]++;
140                     in[belong[k]]++;
141                 }
142             }
143         }
144         for (int i = 1; i <= cnt_3; i++) {
145             if (!in[i] || !out[i])
146                 minn = min(minn, sum[i]);
147         }
148         cout << N * (N - 1) - M - minn * (N - minn) << endl;
149     }
150 }
151 
152 void f3(int a, int b) {
153     if (dfn[a] < dfn[b])
154         swap(a, b);
155     while (dfn[a] > dfn[b])
156     {
157         if (iscut[a])
158             ans--, iscut[a] = 0;
159         a = parent[a];
160     }
161     while (dfn[b] > dfn[a])
162     {
163         if (iscut[b])
164             ans--, iscut[b] = 0;
165         b = parent[b];
166     }
167     while (a != b)
168     {
169         if (iscut[a])
170             ans--, iscut[a] = 0;
171         if (iscut[b])
172             ans--, iscut[b] = 0;
173         a = parent[a], b = parent[b];
174     }
175 }
176 
177 int main()
178 {
179     //freopen("data.txt", "r", stdin);
180 
181     int T;
182     cin >> T;
183     for (int z = 1; z <= T; z++) {
184         printf("Case %d: ", z);
185         init();
186         scanf("%d%d", &N, &M);
187         for (int i = 1; i <= M; i++) {
188             int a, b;
189             scanf("%d%d", &a, &b);
190             add(a, b);
191         }
192         solve();
193     }
194     
195 
196     //freopen("CON", "r", stdin);
197     ////system("pause");
198     return 0;
199 }

扶朕起来

第九题

题目大意应用题基本入门才会做。。机翻一下

PS 有坑。。。很坑

  1 //MADE BY Y_is_sunshine;
  2 //#include <bits/stdc++.h>
  3 //#include <memory.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <sstream>
  9 #include <cstdio>
 10 #include <vector>
 11 #include <string>
 12 #include <cmath>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 
 18 #define INF 0x3f3f3f3f
 19 #define MAXN 110000
 20 
 21 using namespace std;
 22 
 23 struct Edge {
 24     int next;
 25     int to;
 26     int qz;
 27 }edge[MAXN * 4];
 28 
 29 int low[MAXN];
 30 int dfn[MAXN];
 31 int deg[MAXN];
 32 int from[MAXN];
 33 int iscut[MAXN];
 34 int qzcut[MAXN];
 35 int parent[MAXN];
 36 int belong[MAXN];
 37 int instack[MAXN];
 38 int cnt_1;
 39 int cnt_2;
 40 int cnt_3;
 41 int ans;
 42 stack<int> s1;
 43 
 44 void init(void) {
 45     memset(low, 0, sizeof(low));
 46     memset(dfn, 0, sizeof(dfn));
 47     memset(deg, 0, sizeof(deg));
 48     memset(from, 0, sizeof(from));
 49     memset(iscut, 0, sizeof(iscut));
 50     memset(qzcut, 0x3f, sizeof(qzcut));
 51     memset(parent, 0, sizeof(parent));
 52     memset(belong, 0, sizeof(belong));
 53     memset(instack, 0, sizeof(instack));
 54     cnt_1 = 0;
 55     cnt_2 = 0;
 56     cnt_3 = 0;
 57     ans = 0;
 58     while (!s1.empty())
 59         s1.pop();
 60 }
 61 
 62 void add(int x, int y, int c) {
 63     edge[++cnt_1].next = from[x];
 64     edge[cnt_1].to = y;
 65     edge[cnt_1].qz = c;
 66     from[x] = cnt_1;
 67 }
 68 
 69 void tarjan(int x) {
 70     s1.push(x);
 71     instack[x] = 1;
 72     dfn[x] = low[x] = ++cnt_2;
 73 
 74     for (int i = from[x]; i; i = edge[i].next) {
 75         int k = edge[i].to;
 76         if (iscut[k] == 1 && parent[k] == x) {//重边
 77             iscut[k] = 2;
 78         }
 79         if (!dfn[k]) {
 80             parent[k] = x;
 81             tarjan(k);
 82             low[x] = min(low[x], low[k]);
 83             if (dfn[x] < low[k]) {
 84                 iscut[k] = 1;
 85                 qzcut[k] = min(qzcut[k], edge[i].qz);
 86             }
 87         }
 88         else if (parent[x] != k && instack[x])
 89             low[x] = min(low[x], dfn[k]);
 90 
 91     }
 92     if (dfn[x] == low[x]) {
 93         cnt_3++;
 94         int temp;
 95         do {
 96             temp = s1.top();
 97             s1.pop();
 98             belong[temp] = cnt_3;
 99             instack[temp] = 0;
100         } while (temp != x);
101     }
102 }
103 
104 void solve(int N) {
105     ans = INF;
106     int flag2 = 0;
107     for (int i = 1; i <= N; i++)
108         if (!dfn[i])
109             tarjan(i), flag2++;
110     int flag = 1;
111     for (int i = 1; i <= N; i++) {
112         for (int j = from[i]; j; j = edge[j].next) {
113             int k = edge[j].to;
114             if (iscut[k] == 1 && parent[k] == i) {
115                 flag = 0;
116                 ans = min(ans, qzcut[k]);
117             }
118         }
119     }
120     if (flag2 > 1) {
121         cout << 0 << endl;
122     }
123     else if (flag) {
124         cout << -1 << endl;
125     }
126     else if (ans)
127         cout << ans << endl;
128     else
129         cout << 1 << endl;
130 }
131 
132 int main()
133 {
134     //freopen("data.txt", "r", stdin);
135 
136     int N, M;
137     while (cin >> N >> M) {
138         if (!N && !M)
139             break;
140         init();
141         for (int i = 1; i <= M; i++) {
142             int a, b, c;
143             scanf("%d%d%d", &a, &b, &c);
144             add(a, b, c);
145             add(b, a, c);
146         }
147         solve(N);
148 
149     }
150 
151 
152     //freopen("CON", "r", stdin);
153     //system("pause");
154     return 0;
155 }

朕还能学

那么问题来了第八题呢知识点二分图匹配因为没时间了也没有了解二分图没写写了之后补上

我写完了吗？我写完了吗？我写完了吗？

那么是时候吐槽了！！

在学习基本操作的时候花了半天了解图图的结构基本名称

从最基本的dfn low 开始全是java写的 C++写的也看不懂后半天基本0收获

整理太难了

第二天找到一个模板这个模板只能求出belong 也就是强连通分量对还是AC不了一道题的

但是真的改不了了不会改也看不懂其他的

找到一个能看懂的模板以后就再也不想改了也不会改一改就错

第一道题是两天才迷迷糊糊的写出来

更刺激的事情

后面的题目很少用这个模板只能挨个去找看在能改变最少的情况下能找到更符合的不能

像有些用parent数组有些带两个参数有些神奇的存放神奇的判断

每题还能扩展到其他知识点可神奇了~~~

难啊难啊难啊

进度基本一天一道半题像有些tarjan有两个参数什么的求边的求割点的

实话到第四题各种题解就出现了同样的重边数据能跑出各种各样的结果

竟然！！！都能AC 我服了我想ctrl去了

基本到第七题才有了自己的见解才基本入门尝试着去改自己的模板改别人的题解

但是！！！！！！！！！！！！！

对周四了自己的专题还没做完我的另一个小伙伴都是搞到一点的....如实一点

明天整理整理吧周六分享一下

整！理！出！这！些！已！经！很！难！了！

写的不好见谅哈