澳门威利斯人_威利斯人娱乐「手机版」

来自 办公软件 2019-11-16 06:37 的文章
当前位置: 澳门威利斯人 > 办公软件 > 正文

tarjan算法详解,强连通分量

UVA - 11504 Dominos 强连通分量

 

 

题意 :多米诺骨牌 假诺有边存在u -> v 表明u倒了v也自行倒了。问最少须求手动推到多少个。

若果局地牌归于同一个强连通分量 那么自由推倒此中之生龙活虎尽管全体打倒。能够强连通缩点之后 推倒的自然是不曾入度的牌。

 

潜心 那题不能够直接剖断全数入度为0的点有多少个,因为大概存在入度都不为0 不过存在三个强连通分量。举例

n = 6, m = 6

1 -> 2,

2 -> 3,

3 -> 1,

4 -> 5,

5 -> 6,

6 -> 4.

即使尚无入度为0的点 可是急需推2次。

 

 

#pragma comment(linker, /STACK:10240000,10240000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#define mod 4294967296
#define MAX 0x3f3f3f3f
#define lson o<<1, l, m
#define rson o<<1|1, m 1, r
#define SZ(x) ((int)ans.size())
#define MAKE make_pair
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define mem(a) memset(a, 0, sizeof(a))
const double pi = acos(-1.0);
const double eps = 1e-9;
const int N = 100005;
const int M = 20005;
typedef long long ll;
using namespace std;

int n, m;
vector  G[N];
int pre[N], low[N], scc[N], dfs_clock, scc_cnt;
stack  S;
int T;
void dfs(int u) {
    pre[u] = low[u] =   dfs_clock;
    S.push(u);
    for(int i = 0; i < G[u].size(); i  ) {
        int v = G[u][i];
        if(pre[v] == 0) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if(scc[v] == 0) {
            low[u] = min(low[u], low[v]);
        }
    }
    if(low[u] == pre[u]) {
        scc_cnt  ;
        for(;;) {
            int x = S.top(); S.pop();
            scc[x] = scc_cnt;
            if(x == u) break;
        }
    }
}
void find_scc() {
    dfs_clock = scc_cnt = 0;
    mem(scc);
    mem(pre);
    for(int i = 0; i < n; i  ) {
        if(pre[i] == 0) dfs(i);
    }
}
int vis[N];
int main()  {

    //freopen(in.txt,r,stdin);
    cin >> T;
    while(T--) {
        cin >> n >> m;

        for(int i = 0; i < n; i  ) G[i].clear();
        for(int i = 0; i < m; i  ) {
            int x, y;
            scanf(%d%d, &x, &y);
            x--, y--;
            G[x].push_back(y);
        }

        find_scc();

        mem(vis);
        for(int u = 0; u < n; u  ) {
            for(int i = 0; i < G[u].size(); i  ) {
                int v = G[u][i];
                if(scc[v] != scc[u]) {
                    vis[ scc[v] ]  ;
                }
            }
        }
        int cnt = 0;
        //cout << scc_cnt << endl;
        for(int i = 1; i <= scc_cnt; i  ) {
            if(vis[i] == 0) cnt  ;
        }
        cout << cnt << endl;

    }


    return 0;
}

 

 

??

- 11504 Dominos 强连通分量 题意 :多米诺骨牌 假设有边存在u - v 说明u倒了v也自动倒了。问最少要求手动推到多少个。 假设局地牌归于同意气风发...

tarjan算法解说。

tarjan算法,二个关于 图的联通性的美妙算法。基于DFS算法,深度优先搜索一张有向图。!注意!是有向图。依据树,仓库,打标识等种种美妙方法来成功剖析叁个图的劳作。而图的联通性,正是任督二复方亚油酸乙酯胶丸不通。。的难题。

询问tarjan算法早前您须要知道:
强连通,强连通图,强连通分量,解答树(解答树只是一种格局。驾驭就能够卡塔尔国

强连通(strongly connected): 在一个有向图G里,设七个点 a b 发掘,由a有一条路能够走到b,由b又有一条路能够走到a,大家就叫那七个顶峰(a,b卡塔尔强连通。

强连通图: 如若在一个有向图G中,每五个点都强连通,大家就叫这些图,强连通图。

强连通分量strongly connected components):在一个有向图G中,有三个子图,这一个子图每2个点都知足强连通,大家就叫这些子图叫做 强连通分量 [分量::把一个向量分解成多少个方向的向量的和,这一个样子上的向量就叫做该向量(未表达前的向量卡塔 尔(英语:State of Qatar)的轻重]
举个简单的榛子:

图片 1

诸如这一个图,在此个图中吗,点1与点2互相都有门路到达对方,所以它们强连通.

而在此个有向图中,点1 2 3整合的这一个子图,是成套有向图中的强连通分量。

解答树:正是一个方可来表明出递归枚举的方式的树(图卡塔 尔(英语:State of Qatar),其实也得以说是递归图。。反正都以四个作用,多个人展览馆示从“什么都还未做”初叶到“全部结求出来”稳步到位的长河。“进程!”

 

tarjan算法,之所以用DFS正是因为它将每一个强连通分量作为寻找树上的三个子树。而这些图,便是八个整机的搜索树。

为了使那颗找寻树在境遇强连通分量的节点的时候能顺遂进行。每一种点都有多少个参数。

1, DFN[]作为这些点寻觅的次序编号(时间戳卡塔尔国,同理可得就是第多少个被寻觅到的。%各样点的小时戳都分化样%。

2, LOW[]作为各类点在此颗树中的,最小的子树的根,每一遍保障最小,喜欢它的老爸结点的大运戳这种认为。假诺它自个儿的LOW[]最小,那那几个点就应有从新分配,产生这么些强连通分量子树的根节点。
ps:每一遍找到二个新点,这一个点LOW[]=DFN[]。

而为了存款和储蓄整个强连通分量,这里筛选的器皿是,酒店。每回一个新节点现身,就进站,如若那一个点有 出度 就波路壮阔往下找。直到找到底,每便回到上来都看豆蔻梢头看子节点与那一个节点的LOW值,哪个人小就取什么人,保险最小的子树根。借使找到DFN[]==LOW[]就印证这些节点是以此强连通分量的根节点(究竟这些LOW[]值是那些强连通分量里最小的。卡塔 尔(英语:State of Qatar)最后找到强连通分量的节点后,就将以此栈里,比此节点后跻身的节点全体出栈,它们就组成三个簇新的强连通分量。

先来少年老成段伪代码:

tarjan(u){

  DFN[u]=Low[u]= Index // 为节点u设定次序编号和Low初值

  Stack.push(u)   // 将节点u压入栈中

  for each (u, v) in E // 枚举每一条边

    if (v is not visted) // 要是节点v未被访谈过

        tarjan(v) // 继续向下找

        Low[u] = min(Low[u], Low[v])

    else if (v in S) // 借使节点u还在栈内

        Low[u] = min(Low[u], DFN[v])

  if (DFN[u] == Low[u]) // 假使节点u是强连通分量的根

  repeat v = S.pop  // 将v退栈,为该强连通分量中叁个极限

  print v

  until (u== v)

}

先是来一张有向图。网络四处都以以此图。大家就一点一点来效仿整个算法。

图片 2

从1进入 DFN[1]=LOW[1]= ++index ----1

入栈 1

由1进入2 DFN[2]=LOW[2]= ++index ----2

入栈 1 2

之后由2进入3 DFN[3]=LOW[3]= ++index ----3

入栈 1 2 3

之后由3进入 6 DFN[6]=LOW[6]=++index ----4

入栈 1 2 3 6

图片 3

 

 

 

 

 

 

而后察觉6无出度,之后决断DFN[6]==LOW[6]

注明6是个强连通分量的根节点:6及6今后的点 出栈。

栈: 1 2 3 

后来退回 节点3 Low[3] = min(Low[3], Low[6]) LOW[3]还是 3

节点3 也未尝再能拉开的边了,判定DFN[3]==LOW[3]

证实3是个强连通分量的根节点:3及3从此以后的点 出栈。

栈: 1 2 

日后退回 节点2 嗯?!往下到节点5

DFN[5]=LOW[5]= ++index -----5

入栈 1 2 5

图片 4

 

ps:你会发觉在有向图旁边的不得了丑的(划掉卡塔尔寻找树 用红线剪掉的子树,那个正是强连通分量子树。每一趟找到四个。直接。生龙活虎剪刀下去。半个子树就未有了。。

结点5 往下找,开采节点6 DFN[6]有值,被访谈过。就随意它。

三翻五次 5往下找,找到了节点1 他老爹的老爸。。DFN[1]被访谈过同一时间还在栈中,表达1还在这里个强连通分量中,值得发掘。 Low[5] = min(Low[5], DFN[1])

规定关系,在那棵强连通分量树中,5节点要比1节点现身的晚。所以5是1的子节点。So

LOW[5]= 1

由5连任回来2 Low[2] = min(Low[2], Low[5])

LOW[2]=1;

2持续回来1 论断 Low[1] = min(Low[1], Low[2]) 

LOW[1]还是 1

1还会有边未有走过。开采节点4,访谈节点4

DFN[4]=LOW[4]=++index ----6

入栈 1 2 5 4 

由节点4,走到5,开掘5被访问过了,5还在栈里,

Low[4] = min(Low[4], DFN[5]) LOW[4]=5

表达4是5的三个子节点。

图片 5

 

由4回到1.

回到1,判断 Low[1] = min(Low[1], Low[4])

LOW[1]还是 1 。

判断 LOW[1] == DFN[1]

诶?!相等了    表明以1为根节点的强连通分量已经找完了。

将栈中1以至1从此进栈的全体一点点,都出栈。

栈 :(鬼都还没了)

本条时候就完了吗?!

你感觉就完了吧?!

然而并不曾完,万风流倜傥您只走了二遍tarjan整个图未有找完如何是好吧?!

故此。tarjan的调用最佳在循环里化解。

like    假诺这么些点并未有被访问过,那么就从那些点在此在此以前tarjan三遍。

因为这么好让每一种点都被访谈到。

 基本思路:

1.初始化

2.入栈

3.枚举:

    1.不在队列中->访谈,进行赋值,

    2.在队列中->赋值

4.寻找根->输出结果

来生龙活虎道裸代码。

输入:
一个图有向图。

输出:
它每一个强连通分量。

以此图正是刚刚讲的不行图。完全一样。

input:

6 8

1 3

1 2

2 4

3 4

3 5

4 6

4 1

5 6

output:

6

5

3 4 2 1

a Sans Unicode"; mso-hansi-font-family:"Lucida Sans Unicode";mso-bidi-font-family:"Lucida Sans Unicode"; color:black'>的一个子节点。

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
struct node {
    int v,next;
} edge[1001];
int DFN[1001],LOW[1001];
int stack[1001],heads[1001],visit[1001],cnt,tot,index;
void add(int x,int y) {
    edge[  cnt].next=heads[x];
    edge[cnt].v = y;
    heads[x]=cnt;
    return ;
}
void tarjan(int x) { //代表第几个点在处理。递归的是点。
    DFN[x]=LOW[x]=  tot;// 新进点的初始化。
    stack[  index]=x;//进站
    visit[x]=1;//表示在栈里
    for(int i=heads[x]; i!=-1; i=edge[i].next) {
        if(!DFN[edge[i].v]) {
            //如果没访问过
            tarjan(edge[i].v);//往下进行延伸,开始递归
            LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,涉及到强连通分量子树最小根的事情。
        } else if(visit[edge[i].v ]) {
            //如果访问过,并且还在栈里。
            LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子/父亲。就是链接对应关系
        }
    }
    if(LOW[x]==DFN[x]) { //发现是整个强连通分量子树里的最小根。
        do {
            printf("%d ",stack[index]);
            visit[stack[index]]=0;
            index--;
        } while(x!=stack[index 1]);//出栈,并且输出。
        printf("n");
    }
    return ;
}
int main() {
    memset(heads,-1,sizeof(heads));
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1; i<=m; i  ) {
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1; i<=n; i  )
        if(!DFN[i])  tarjan(1);//当这个点没有访问过,就从此点开始。防止图没走完
    return 0;
}

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

struct node
{
    int u;
    int v;
    int w;
    int next;
}edge[101];
int head[101];
int num=1;
void add(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].next=head[x];
    head[x]=num  ;
}
int dfn[1001];// 既可以用来表示一个点的被访问的顺序,又可以判断是否出现过 
int low[1001];
int stack[101];
int top=0;
int now=0;//  已经访问的数的数量 
int vis[1001];//表示是否在栈中 
void tarjan(int x)
{

    vis[x]=1;
    dfn[x]=low[x]=  now;
    stack[  top]=x;
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        if(!dfn[edge[i].v])
        {
            tarjan(edge[i].v);
            low[x]=min(low[x],low[edge[i].v]);
        }
        else if(vis[edge[i].v])
        {
            low[x]=min(low[x],dfn[edge[i].v]);
        }
    }
    if(low[x]==dfn[x])
    {
        do
        {
            printf("%d ",stack[top]);
            vis[stack[top]]=0;
            top--;
        }while(x!=stack[top 1]);
        putchar('n');
    }
    return;
}
int main()
{

    for(int i=1;i<=101;i  )
    head[i]=-1;
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i  )
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i  )
    {
        if(dfn[i]==0)
        {
            tarjan(i);
        }
    }
    return 0;

}

 

本文由澳门威利斯人发布于办公软件,转载请注明出处:tarjan算法详解,强连通分量

关键词: 澳门威利斯人