Graph Algorithm

Comments

Post a Comment

Popular posts from this blog

LightOJ-1026 Critical Links Solutions C++

  #include<bits/stdc++.h> #define vi vector<int> #define pb push_back using namespace std; vi g[10005]; int visit[10005],low[10005],in[10005]; vector<pair<int,int> > bridge; int cnt,timer; void dfs1(int s,int p) {     visit[s]=1;     low[s]=in[s]=++timer;     for(int i=0;i<g[s].size();i++)     {         if(g[s][i]==p)             continue;         else if(visit[g[s][i]])             low[s]=min(in[g[s][i]],low[s]);         else         {             dfs1(g[s][i],s);             if(low[g[s][i]]>in[s])             {                 cnt++;                 if(g[s][i]>s)                 bridge.pb(make_pair(s,g[s][i]));                 else                 bridge.pb(make_pair(g[s][i],s));             }             low[s]=min(low[g[s][i]],low[s]);         }     } } int main() {     int t,n,e,u,v,cs=0;     char a,b,c;     cin>>t;     while(t--)     {         cnt=0,timer=0;         cin>>n;        for(int i=0;i<n;i++)        {            g[i].clear(
Read more