分类存档：默认分类

首先提出图的转置的概念。所谓转置就是将一个图上所有的有向边反向。简单来说就是本是x->y的一条边，现在变为y->x这样一条边。

另外强连通性质具有传递性，如果(i,j),(j,k)属于同一强连通分量，那么(i,k)属于同一强连通分量。因为如果满足题设，那么存在路径i->j->k和k->j->i。所以传递性得证。所以其实我们要求点i所属的极大强连通分量，只需要把所有和i可以互达的点求出来就可以了。

该算法的流程如下:

1、 利用深度优先搜索遍历原图，并按出栈的先后顺序把点放进一个线性表里。这里可以每次取任意一个点出发DFS,如果还有点未被DFS到，那么继续任选未被遍历到的点出发DFS。

2、 将整个图转置。

3、 按照线性表中的出栈顺序，从后往前依次作为起点DFS。每次DFS到的就是一个强连通分量。

初看这个算法很神奇，但是其实是不难证明的。

命题1：该算法求出的都是强连通分量

假设在后来转置后的图中从x dfs到了 y处，说明存在路径x->y。因为这是在转置图中，所以说明原图中存在路径y->x。

然后另外一个信息就是x的序号在y之后。这有两种可能：

1、以y为根先DFS出了一棵搜索树(可以认为是整个搜索树的一棵子树)，但是这棵子树里不包含x，并且此时x还未被dfs到。（利用反证法，如果这棵子树里包含了x，那么x的序号会在y之前）

2、y是x扩展出来的搜索树中的一个结点。

综合两个条件，综合两个条件取交。那么上面两种可能中的第一种不成立。因为存在路径y->x，所以如果x未被dfs到，一定会被y为根的搜索树包含的。于是只剩下第二种可能，那么第二种情况表明存在路径x->y。所以x,y可以互相到达。至此证明了该算法求出的都是强连通分量。命题1得证。

命题2：所有的极大强连通分量都会被该算法求到。

命题2等价于：不存在两个点(i,j)，他们互相可达，但是没有被放进同一个强连通分量中。易知若(i,j)可以互相到达，那么肯定其中一个点在另外一个点扩展出去的搜索树中(注意DFS的性质，走完一个分叉再走另外一个分叉)。

由于轮换对称，不妨设j在i扩展出去的搜索树中，那么显然j比i先出栈。假如命题2不成立，那么必须是有一棵以A为根(而且这个A必须比i后出栈)的搜索树，它包含了j但不包含i。由命题1可知，(A,j)可互达。那么由于(i,j)可互达，在这颗搜索树中，肯定能有j扩展到i，所以这样的一棵搜索树是不存在的。因此反证得命题2成立。

该算法比Tarjan算法慢一点，但是有一个好处：该算法依次求出的强连通分量已经是拓扑序的。

下面给出这一性质的证明：

对于两个不同的强连通分量A,B,设A中出栈顺序最晚的点为a,B中出栈顺序最晚的点为b。不妨设a出栈顺序在b之前，那么有两种可能。

1、存在路径b->a。由于两点不属于同一强连通分量，所以不存在路径a->b。这种情况下Kosaraju算法会先把B强连通分量拿出来，所以是满足拓扑序的。

2、不存在路径b->a。那么这种情况下必然也不存在路径a->b，否则a出栈之时，b必然已经出栈了。所以，先拿出B强连通分量是符合拓扑序的。

所以，该性质得证。

【写图论教程时无聊证了一下。。。各位无视】

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=2815

【题目大意】给定a,p,c让你求满足 a^x = c (mod p)的最小非负整数解

【算法分析】

详细的讲解：

【扩展Baby Step Giant Step解决离散对数问题】http://hi.baidu.com/aekdycoin/blog/item/b317ca18bb24334942a9ad55.html

By AekdyCoin

【Result】

33876852011-01-11 07:23:30Accepted2815421MS928K2498 BG++edward_mj

【吐槽】

倒3的时间。

分析一下原因：

1、cin。其实这个应该没有任何影响。

2、memset了hash的数组。

3、exgcd用了lld。

。。。这种速度绝对不能作为模板了= =

【CODE】

#include #include #include #include #include using namespace std;
typedeflong long lld;
constint N=100003;

struct Baby_step_Giant_step{
       struct edge{int key,times;edge*next;}g[N],*ls[N];
       int e;
      
       void add(int x,int times){
            int hash=x%N;
            for(edge*t=ls[hash];t;t=t->next)
              if(t->key==x)return;
            g[++e].key=x; g[e].times=times; g[e].next=ls[hash]; ls[hash]=&g[e];
       }
      
       int In(int x){
           int hash=x%N;
           for(edge*t=ls[hash];t;t=t->next)
             if(t->key==x)return t->times;
           return–1;
       }
      
       int Power_mod(int a,int b,int Mod){
           lld t=a,res=1;
           while(b){
                 if(b&1) res=res*t%Mod;
                 t=t*t%Mod;
                 b>>=1;
           }
           return(int)(res);
       }
      
       lld exgcd(int a,int b,lld&x,lld&y){
           if(b==0){
             x=1;
             y=0;
             return a;
           }
           lld g=exgcd(b,a%b,x,y);
           lld tx=x,ty=y;
           x=ty;
           y=tx–a/b*ty;
           return g;
       }
      
       int  solve(int a,int c,int p){
            if(c>=p)return–1;
            int i,j;
            int x=1;
            int t=1;
            int s=(int)ceil(sqrt((double)p));
            int res;
            int cnt=0;
            lld tx,ty,g;
            for(i=0;i<=50;i++)if(Power_mod(a,i,p)==c)return i;
           
            while((g=exgcd(a,p,tx,ty))!=1){
                  if(c%g)return–1;
                  c/=g;
                  p/=g;
                  x=(lld)(a)/g*x%p;
                  cnt++;
            }
           
            e=0;
            memset(ls,0,sizeof(ls));
            for(i=0;i<s;i++) add(Power_mod(a,i,p),i);
           
            for(int step=Power_mod(a,s,p),i=cnt;i<p;i+=s,x=(lld)(x)*step%p){
                g=exgcd(x,p,tx,ty);
                tx=tx*c%p;
                if(tx<0) tx+=p;
                res=In((int)tx);
                if(res==-1)continue;
                return res+i;
            }
            return–1;
       }     
}Number_Theory;

intmain(){
    int a,p,c;
    while(cin>> a>> p>> c){
      int ans=Number_Theory.solve(a,c,p);
      if(ans==-1) puts("Orz,I can’t find D!");
              else printf("%dn",ans);
    }
}

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=3664

【题目大意】

输入n和k。

输出n的所有排列里有多少个是Ai>i的数量等于k的。

【算法分析】

递推。

F[n,k]表示对应答案。

然后F[n,k]=F[n-1,k]*(k+1)+F[n-1,k-1]*((n-1) – (k-1))

本质是现在多一个数字n，也多了一个位置An。

从F[n-1,k]那里继承过来的是用n去填那些已经满足Ai>i的位置，因为现在n是最大的，所以填进去以后肯定也是满足Ai>i的，然后原本对应位置的数字就填到An上。因为可以填本身An这个位置，所以系数+1。

从F[n-1,k-1]那里继承过来的是用n去和前面那些满足Ai<=i的位置上的数交换，因为现在n是最大的，所以填了以后显然满足Ai>i。

【Hint】

必须打表才能过。

【CODE】

http://xiudaima.appspot.com/code/detail/4344003