fork(1) download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int n,m;
  6. vector<int> vis;
  7.  
  8. bool dfs(int w0,int w,vector<vector<int>> &G) {
  9. vis[w0]=1;
  10. for (int q=1; q<=n; q++) {
  11. if (G[w0][q]>0 && vis[q]==0) {
  12. if (q==w || dfs(q,w,G)==0) {
  13. G[w0][q]--;
  14. G[q][w0]++;
  15. return 0;
  16. }
  17. }
  18. }
  19. return 1;
  20. }
  21.  
  22. int main() {
  23. int u,v,i,k,res=10000000;
  24. scanf("%d %d\n",&n,&m);
  25. vector<vector<int>> G0(n+1,vector<int>(n+1,0));
  26. for (i=0; i<m; i++) {
  27. scanf("%d %d\n",&u,&v);
  28. G0[u][v]=1;
  29. G0[v][u]=1;
  30. }
  31. for (i=2; i<=n; i++) {
  32. k=0;
  33. vector<vector<int>> G=G0;
  34. vis=vector<int>(n+1,0);
  35. while (!dfs(1,i,G)) {
  36. k++;
  37. vis=vector<int>(n+1,0);
  38. }
  39. if (k<res) res=k;
  40. }
  41. printf("%d",res);
  42. return 0;
  43. }
Success #stdin #stdout 0s 15240KB
stdin
5 5 
1 2 
2 3 
3 5 
5 2 
2 4
stdout
1