#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <utility> #include <queue> #include <vector> #include <string> #include <cstring> #define REP(a,n) for (int a = 0; a<(n); ++a) #define FOR(a,b,c) for (int a = (b); a<=(c); ++a) #define FORD(a,b,c) for (int a = (b); a>=(c); --a) #define FOREACH(a,v) for (auto a : v) #define MP make_pair #define PB push_back template<class T> inline int size(const T&t) { return t.size(); } using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<string> vs; typedef long long LL; /////////////////////////////// #define MAXN 200000 #define MAXKRAW 500000 int N, M; int kraw[MAXKRAW][2]; vi inc[MAXN]; int del1, del2; LL res; int odw, mosty, czas; bool vis[MAXN]; int tin[MAXN], low[MAXN]; void DFS(int x, int my_kr) { vis[x] = 1; ++odw; tin[x] = low[x] = czas++; for (int k : inc[x]) { if (k == my_kr || k == del1 || k == del2) continue; int ch = kraw[k][kraw[k][0] == x ? 1 : 0]; if (!vis[ch]) { DFS(ch, k); if (low[ch] > tin[x] && k > del2) ++mosty; } low[x] = min(low[x], low[ch]); } } int main() { std::ios::sync_with_stdio(false); cin >> N >> M; REP(k, M) REP(b, 2) { cin >> kraw[k][b]; --kraw[k][b]; inc[kraw[k][b]].PB(k); } if (M <= N + 1 || N > 1000) res = M * (LL)(M - 1) * (M - 2) / 6; else for (del1 = 0; del1 <= M - 3; ++del1) for (del2 = del1 + 1; del2 <= M - 2; ++del2) { REP(a, N) vis[a] = 0; odw = mosty = czas = 0; DFS(0, -1); if (odw < N) res += M - 1 - del2; else res += mosty; } cout << res << endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <utility> #include <queue> #include <vector> #include <string> #include <cstring> #define REP(a,n) for (int a = 0; a<(n); ++a) #define FOR(a,b,c) for (int a = (b); a<=(c); ++a) #define FORD(a,b,c) for (int a = (b); a>=(c); --a) #define FOREACH(a,v) for (auto a : v) #define MP make_pair #define PB push_back template<class T> inline int size(const T&t) { return t.size(); } using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<string> vs; typedef long long LL; /////////////////////////////// #define MAXN 200000 #define MAXKRAW 500000 int N, M; int kraw[MAXKRAW][2]; vi inc[MAXN]; int del1, del2; LL res; int odw, mosty, czas; bool vis[MAXN]; int tin[MAXN], low[MAXN]; void DFS(int x, int my_kr) { vis[x] = 1; ++odw; tin[x] = low[x] = czas++; for (int k : inc[x]) { if (k == my_kr || k == del1 || k == del2) continue; int ch = kraw[k][kraw[k][0] == x ? 1 : 0]; if (!vis[ch]) { DFS(ch, k); if (low[ch] > tin[x] && k > del2) ++mosty; } low[x] = min(low[x], low[ch]); } } int main() { std::ios::sync_with_stdio(false); cin >> N >> M; REP(k, M) REP(b, 2) { cin >> kraw[k][b]; --kraw[k][b]; inc[kraw[k][b]].PB(k); } if (M <= N + 1 || N > 1000) res = M * (LL)(M - 1) * (M - 2) / 6; else for (del1 = 0; del1 <= M - 3; ++del1) for (del2 = del1 + 1; del2 <= M - 2; ++del2) { REP(a, N) vis[a] = 0; odw = mosty = czas = 0; DFS(0, -1); if (odw < N) res += M - 1 - del2; else res += mosty; } cout << res << endl; } |