Guest User

Untitled

a guest
Jul 22nd, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8. const int maxn = 100;
  9. bool visited[maxn];
  10. vector<int> edges[maxn];
  11. int intime[maxn];
  12. int lowlink[maxn];
  13. int n,m;
  14. int ttime = 1;
  15.  
  16. set< pair<int,int> > bridges;
  17. map< pair<int,int>,int > mmap;
  18.  
  19. void dfs(int v,int p)
  20. {
  21.    if(visited[v])return;
  22.    visited[v]=true;
  23.    intime[v]=ttime;
  24.    lowlink[v]=ttime++;
  25.    for(int i =0;i<edges[v].size();i++)
  26.    {
  27.        int child = edges[v][i];
  28.        if(child == p)continue;
  29.        if(visited[child])
  30.        {
  31.            lowlink[v] = min(lowlink[v],intime[child]);
  32.        }
  33.        else
  34.        {
  35.            dfs(child,v);
  36.            lowlink[v] = min(lowlink[v],lowlink[child]);
  37.  
  38.            if(lowlink[v]<lowlink[child])
  39.            {
  40.                bridges.insert(make_pair(min(v,child),max(v,child)));
  41.            }
  42.        }
  43.    }
  44. }
  45.  
  46. int main()
  47. {  
  48.     freopen("input.txt","r",stdin);
  49.     freopen("output.txt","w",stdout);
  50.     cin>>n>>m;
  51.    int i,j,k;
  52.    for(i = 0;i<m;i++)
  53.    {
  54.        cin>>j>>k;
  55.        edges[j].push_back(k);
  56.        edges[k].push_back(j);
  57.        mmap[make_pair(min(j,k),max(j,k))]= i+1;
  58.    }
  59.    for(i =1;i<=n;i++)
  60.        if(!visited[i])
  61.            dfs(i,-1);
  62.  
  63.    cout<<bridges.size()<<endl;
  64.    i = 0;
  65. vector<int> t;
  66.    for(set< pair<int,int> >::iterator iter = bridges.begin();iter!=bridges.end();iter++)
  67.    {
  68.         t.push_back(mmap[(*iter)]);
  69.    }
  70.    sort(t.begin(),t.end());
  71.     for(i = 0;i<t.size();i++)
  72.     {
  73.         cout<<t[i];
  74.        if(i!=t.size()-1)cout<<endl;
  75.     }
  76.    return 0;
  77. }
Add Comment
Please, Sign In to add comment