#include <bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=5e5+5; bitset<MAX> O; bitset<MAX>O2; vector<pii>P[MAX]; int ojciec[MAX]; int ans=0; bool drzewowa[MAX]; int low[MAX]; int czas[MAX]; int times=1; int n,m; void dfs(int u,int fa){ //cout<<"TERAZ "<<u<<" "<<fa<<"\n"; ojciec[u]=fa; O2[u]=true; czas[u]=times++; low[u]=czas[u]; for (auto it:P[u]){ int v=it.st,numer=it.nd; //if (O[5] && O[6] && !O[numer] && !O2[v])cout<<"TERAZ "<<u<<" "<<v<<" "<<numer<<"\n"; if (!O[numer] && !O2[v])drzewowa[numer]=true,dfs(v,u),low[u]=min(low[u],low[v]); else if (!drzewowa[numer] && !O[numer]){ low[u]=min(low[u],czas[v]); } } } void check(){ //cout<<"POJEDYNCZY\n"; int spojne=0; times=1; for (int i=1;i<=n;i++)O2[i]=false; for (int i=1;i<=m;i++)drzewowa[i]=false; for (int i=1;i<=n;i++){ if (spojne==1 && !O2[i]){ans+=m-2;return;} if (!O2[i])spojne++,dfs(i,-1); } for (int i=1;i<=n;i++){ if (ojciec[i]==-1)continue; //if (O[5] && O[6]){ // cout<<"KURWA "<<i<<" "<<czas[i]<<"\n"; //} if (low[i]>czas[ojciec[i]])ans++; } } int32_t main(){ BOOST; cin>>n>>m; for (int i=1;i<=m;i++){ int a,b; cin>>a>>b; P[a].pb(mp(b,i)); P[b].pb(mp(a,i)); } for (int i=1;i<=m;i++){ for (int j=1;j<=m;j++){ if (i==j)continue; O[i]=true; O[j]=true; //<<"HEH "<<i<<" "<<j<<"\n"; check(); O[i]=false; O[j]=false; } } cout<<ans/6; return 0; }
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 84 85 | #include <bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=5e5+5; bitset<MAX> O; bitset<MAX>O2; vector<pii>P[MAX]; int ojciec[MAX]; int ans=0; bool drzewowa[MAX]; int low[MAX]; int czas[MAX]; int times=1; int n,m; void dfs(int u,int fa){ //cout<<"TERAZ "<<u<<" "<<fa<<"\n"; ojciec[u]=fa; O2[u]=true; czas[u]=times++; low[u]=czas[u]; for (auto it:P[u]){ int v=it.st,numer=it.nd; //if (O[5] && O[6] && !O[numer] && !O2[v])cout<<"TERAZ "<<u<<" "<<v<<" "<<numer<<"\n"; if (!O[numer] && !O2[v])drzewowa[numer]=true,dfs(v,u),low[u]=min(low[u],low[v]); else if (!drzewowa[numer] && !O[numer]){ low[u]=min(low[u],czas[v]); } } } void check(){ //cout<<"POJEDYNCZY\n"; int spojne=0; times=1; for (int i=1;i<=n;i++)O2[i]=false; for (int i=1;i<=m;i++)drzewowa[i]=false; for (int i=1;i<=n;i++){ if (spojne==1 && !O2[i]){ans+=m-2;return;} if (!O2[i])spojne++,dfs(i,-1); } for (int i=1;i<=n;i++){ if (ojciec[i]==-1)continue; //if (O[5] && O[6]){ // cout<<"KURWA "<<i<<" "<<czas[i]<<"\n"; //} if (low[i]>czas[ojciec[i]])ans++; } } int32_t main(){ BOOST; cin>>n>>m; for (int i=1;i<=m;i++){ int a,b; cin>>a>>b; P[a].pb(mp(b,i)); P[b].pb(mp(a,i)); } for (int i=1;i<=m;i++){ for (int j=1;j<=m;j++){ if (i==j)continue; O[i]=true; O[j]=true; //<<"HEH "<<i<<" "<<j<<"\n"; check(); O[i]=false; O[j]=false; } } cout<<ans/6; return 0; } |