#include <bits/stdc++.h> #define pb push_back #define ff first #define ss second const int N=200000; const int M=500000; using namespace std; bool f[M]; int n,m,a,b,c,v[N],w; vector <pair<int,int>> g[N]; int dfs(int a) { int w=1; v[a]=c; for (auto i: g[a]) { if (!f[i.ss] && v[i.ff]<c) { w+=dfs(i.ff); } } return w; } int main() { scanf("%d %d",&n,&m); for (int i=0; i<m; i++) { scanf("%d %d",&a,&b); g[a-1].pb({b-1,i}); g[b-1].pb({a-1,i}); } for (int i=0; i<m; i++) { f[i]=1; for (int j=i+1; j<m; j++) { f[j]=1; for (int k=j+1; k<m; k++) { f[k]=1; c++; if (dfs(0)<n) { w++; } f[k]=0; } f[j]=0; } f[i]=0; } printf("%d\n",w); 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 | #include <bits/stdc++.h> #define pb push_back #define ff first #define ss second const int N=200000; const int M=500000; using namespace std; bool f[M]; int n,m,a,b,c,v[N],w; vector <pair<int,int>> g[N]; int dfs(int a) { int w=1; v[a]=c; for (auto i: g[a]) { if (!f[i.ss] && v[i.ff]<c) { w+=dfs(i.ff); } } return w; } int main() { scanf("%d %d",&n,&m); for (int i=0; i<m; i++) { scanf("%d %d",&a,&b); g[a-1].pb({b-1,i}); g[b-1].pb({a-1,i}); } for (int i=0; i<m; i++) { f[i]=1; for (int j=i+1; j<m; j++) { f[j]=1; for (int k=j+1; k<m; k++) { f[k]=1; c++; if (dfs(0)<n) { w++; } f[k]=0; } f[j]=0; } f[i]=0; } printf("%d\n",w); return 0; } |