tarjan 求强连通分量:
- #include<cstdio>
- #include<iostream>
- #include<cstdlib>
- #define N 1000000
- #include<vector>
- vector <int> scc;
- int sta[N],dfn[N],low[N],in[N],tar[N],tot,tp,cnt;
- void tarjan(int x)
- {
- dfn[x]=low[x]=++tot;
- sta[++tp]=x;
- in[x]=1;
- for(int i=head[x];i;i=e[i].nxt)
- {
- if(!dfn[e[i].to])
- {
- tarjan(e[i].to);
- low[x]=min(low[x],low[e[i].to]);
- }
- else if(in[e[i].to])
- {
- low[x]=min(low[x],dfn[e[i].to]);
- }
- }
- if(dfn[x]==low[x])
- {
- int y;
- cnt++;
- do{
- y=sta[tp--];
- in[y]=0;
- tar[y]=cnt;
- scc[cnt].push_back(y);
- }while(x!=y);
- }
- }
tarjan 缩点:
拓扑排序的思想
代码:
- #include<cstdio>
- #include<iostream>
- #include<cstdlib>
- #include<queue>
- #define N 100000
- using namespace std;
- int in[N],dfn[N],low[N],sta[N],tot,tp,cnt,nmb,head[N],nmb2;
- int n,m,p[N],h[N],tar[N],inn[N],dist[N];
- struct node{
- int to,nxt,from;
- }e[N<<1],e2[N<<1];
- void add(int from,int to)
- {
- e[++nmb]= (node) {to,head[from],from};
- head[from]=nmb;
- }
- void add2(int from,int to)
- {
- e2[++nmb2]= (node) {to,h[from],from};
- h[from]=nmb2;
- }
- void tarjan(int x)
- {
- dfn[x]=low[x]=++tot;
- sta[++tp]=x;
- in[x]=1;
- for(int i=head[x];i;i=e[i].nxt)
- {
- int v=e[i].to;
- if(!dfn[v])
- {
- tarjan(v);
- low[x]=min(low[x],low[v]);
- }
- else if(in[v])
- {
- low[x]=min(low[x],dfn[v]);
- }
- }
- if(dfn[x]==low[x])
- {
- int y;
- while(y=sta[tp--])
- {
- tar[y]=x;
- in[y]=0;
- if(x==y)break;
- p[x]+=p[y];
- }
- }
- }
- int topo()
- {
- queue <int> q;
- for(int i=1;i<=n;i++)
- if(tar[i]==i&&!inn[i])
- {
- q.push(i);
- dist[i]=p[i];
- }
- while(q.size())
- {
- int x=q.front();
- q.pop();
- for(int i=h[x];i;i=e2[i].nxt)
- {
- int y=e2[i].to;
- dist[y]=max(dist[x]+p[y],dist[y]);
- inn[y]--;
- if(inn[y]==0)q.push(y);
- }
- }
- int ans=0;
- for(int i=1;i<=n;i++)ans = max(ans,dist[i]);
- return ans;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)scanf("%d",&p[i]);
- for(int i=1,x,y;i<=m;i++)
- {
- scanf("%d%d",&x,&y);
- add(x,y);
- }
- for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i);
- for(int i=1;i<=m;i++)
- {
- int x=tar[e[i].from] , y=tar[e[i].to];
- if(x!=y)
- {
- add2(x,y);
- inn[y]++;
- }
- }
- printf("%d\n",topo());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3204749.html