精华内容
下载资源
问答
  • 有向图的强连通分支: 算法思想: 1对图G进行深度优先搜索,求出每个顶点的后续遍历序号postn 2反转图G中的,构造一个新的有向图G* 3第2步中产生的森林中的每一颗,对应一个强连通分支 真正算法实现: 1对逆图G...
    /*
    有向图的强连通分支:
    算法思想:
    1对图G进行深度优先搜索,求出每个顶点的后续遍历序号postn
    2反转图G中的边,构造一个新的有向图G*
    3第2步中产生的森林中的每一颗数,对应一个强连通分支
    
    真正算法实现:
    1对逆图G进行后序遍历
    2反转逆图G中的边
    3将统计连通分支数
    
    采用邻接矩阵实现
    输入
    6
    0 1 1 0 0 0
    0 0 0 1 0 0
    0 0 0 1 1 0
    1 0 0 0 0 1
    0 0 0 0 0 1
    0 0 0 0 0 0
    输出:
    3
    
    对逆图后序编号
    算法过程:
    1初始化变量
    2计算逆后序,通过访问标记来实现有无访问过。通过前序与后序两个来
    标记,而且后序的生成是不需要if条件的,因为他必须生成
    3清空前序计数器,设定每个点的强联通分量为-1
    4第二次dfs不再根据访问标记决定是否递归,而是根据当前结点的强连通分量
    5递归的条件必须同时满足两结点连接和该结点的连通分量不为初始值
    */
    
    /*
    关键:
    1 采用先逆序图的后序->原图的后序从高到低的次序做
    
    2 先逆序图的后序中,注意由于是邻接矩阵,只需将<u,k>变成对<k,u>的判断即可,判断包含:是否访问+两点是否连接这两个条件
    	//置已经访问标记
    	g_iVisitArr[u] = 1;
    	for(int k = 0 ; k < n ; k++)
    	{
    		//如果顶点k没有被访问过且<k,u>是一条边,本来是g_r[u][k]
    		if(!g_iVisitArr[k] && g_iMatrix[k][u] == 1)
    		{
    			dfsPost(k,n);
    		}
    	}
    	//注意不管条件如何,每次进入的点都需要加入到后序结点数组中
    	g_vecPost.push_back(u);
    3 正常图中,我们采用一个连通计数器来记录不同节点所处不同的连通分量重
    	//设置连通分量计数器
    	g_iBranchNumArr[u] = g_iBranchCount;
    	for(int k = 0 ; k < n ; k++)
    	{
    		//如果<u,k>连通,且当前结点l连通度为初始值,说明还需要递归;如果不连,或者连通度不为初始值都说明已经遍历过了
    		if(g_iMatrix[u][k] == 1 && g_iBranchNumArr[k] == -1 )
    		{
    			dfs(k,n);
    		}
    	}
    */
    
    
    #include <iostream>
    #include <string.h>
    #include <vector>
    
    using namespace std;
    
    const int MAXSIZE = 10;
    //int g_iMatrix[MAXSIZE][MAXSIZE];
    //int g_iMatrix[7][7]=
    //{
    //0,0, 0, 0, 0, 0, 0,
    //0,0, 1, 1, 0, 0, 0,
    //0,0, 0, 0, 1, 0, 0,
    //0,0, 0, 0, 1, 1, 0,
    //0,0, 0, 0, 0, 0, 1,
    //0,0, 0, 0, 0, 0, 1,
    //0,0, 0, 0, 0, 0, 0
    //};
    
    int g_iMatrix[6][6]=
    {
    0, 1, 1, 0, 0, 0,
    0, 0, 0, 1, 0, 0,
    0, 0, 0, 1, 1, 0,
    1, 0, 0, 0, 0, 1,//粗心看错,导致调试一个下午
    0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0
    };
    int g_iVisitArr[MAXSIZE];
    int g_iPostArr[MAXSIZE];
    vector<int> g_vecPost;
    int g_iBranchCount;
    int g_iBranchNumArr[MAXSIZE];
    
    //逆后序
    void dfsPost(int u,int n)
    {
    	//置已经访问标记
    	g_iVisitArr[u] = 1;
    	for(int k = 0 ; k < n ; k++)
    	{
    		//如果顶点k没有被访问过且<k,u>是一条边,本来是g_r[u][k]
    		if(!g_iVisitArr[k] && g_iMatrix[k][u] == 1)
    		{
    			dfsPost(k,n);
    		}
    	}
    	//注意不管条件如何,每次进入的点都需要加入到后序结点数组中
    	g_vecPost.push_back(u);
    }
    
    //正向遍历
    void dfs(int u,int n)
    {
    	//设置连通分量计数器
    	g_iBranchNumArr[u] = g_iBranchCount;
    	for(int k = 0 ; k < n ; k++)
    	{
    		//如果<u,k>连通,且当前结点l连通度为初始值,说明还需要递归;如果不连,或者连通度不为初始值都说明已经遍历过了
    		if(g_iMatrix[u][k] == 1 && g_iBranchNumArr[k] == -1 )
    		{
    			dfs(k,n);
    		}
    	}
    }
    
    int Kosaraju(int n)
    {
    	//逆序图后序遍历
    	memset(g_iVisitArr,0,sizeof(g_iVisitArr));
    	g_vecPost.clear();
    	for(int k = 0 ; k < n ; k++)
    	{
    		if(!g_iVisitArr[k])
    		{
    			dfsPost(k,n);
    		}
    	}
    	g_iBranchCount = 0;
    	//易错,设定初始强连通度
    	memset(g_iBranchNumArr,-1,sizeof(g_iBranchNumArr));
    	//正向遍历,从顶点最大到最小遍历
    	for(int k = g_vecPost.size() - 1 ; k >= 0 ; k--)
    	{
    		int iPostNum = g_vecPost[k];
    		if(g_iBranchNumArr[iPostNum] == -1)
    		{
    			dfs(iPostNum,n);
    			++g_iBranchCount;
    		}
    	}
    	return g_iBranchCount;
    }
    
    
    void process()
    {
    	int n;
    	int iVal;
    	while(cin >> n)
    	{
    		//for(int i = 1 ; i <= n ; i++)
    		//{
    		//	for(int j = 1 ; j <= n ; j++)
    		//	{
    		//		cin >> iVal;
    		//		g_iMatrix[i][j] = iVal;
    		//	}
    		//}
    		int iRet = Kosaraju(n);
    		cout << iRet << endl;
    	}
    }
    
    int main(int argc,char* argv[])
    {
    	process();
    	getchar();
    	return 0;
    }

    展开全文
  • 6.4图的存储结构创建 存储结构 便于判断是否有边 便于计算度 便于增删 利用空间 统计边数 邻接矩阵 √ √ × × × 邻接表 × × √ √ √ 十字链表 √ √ √ √ 邻接多重表 √ √ √ √ 6.4.1 ...

    笔记目录
    1.1~1.4-数据结构基础概念和时间复杂度
    2.1~2.8-顺序表、链表
    6.4 -图的储存结构与创建

    6.4图的存储结构与创建

    存储结构 便于判断是否有边 便于计算度 便于增删 利用空间 统计边数
    邻接矩阵 × × ×
    邻接表 × ×
    十字链表
    邻接多重表

    6.4.1 邻接矩阵(Adjacency Matrix)

    • /ə’dʒeɪsənsɪ/
    • /ˈmeɪtrɪks/
    • 边edge、aec
    • 顶点vertex

    1、存储

    #define MAX_INT 32767 //int在32位中能取得的最大值表示∞,64位中为 2,147,483,647
    #define MAX_VEX 100   //vertex最大顶点数
    typedef char vertexType; //顶点数据类型
    typedef int arcType      //边  权值类型
    typedef struct{
        vertexType vexs[MAX_VEX];//顶点表
        arctype    arcs[MAX_VEX][MAX_VEX];//邻接矩阵
        int vexNum, arcNum;//当前顶点数,边数
    }AMGraph;
    

    2、创建无向图

    void createAMGraph(AMGraph *G)
    {
    	int i,j,k,w;
        /* 输入顶点数和边数 */
    	printf("输入顶点数和边数:\n");
    	scanf("%d,%d",&G->vexNum,&G->arcNum); 
        
        /* 读入顶点信息,建立顶点表 如顶点名字*/
    	for(i = 0;i <G->vexNum;i++) 
    		scanf(&G->vexs[i]);
        
        /* 初始化 */
    	for(i = 0;i <G->vexNum;i++)
    		for(j = 0;j <G->vexNum;j++)
    			G->arcs[i][j]=MAX_INT;	//默认可为0
        
        /* 用边数,建立邻接矩阵 */
    	for(k = 0;k <G->arcNum;k++) 
    	{
    		printf("输入边(vi,vj)上的上标i,下标j和权w:\n");
    		scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */
    		G->arcs[i][j]=w; 
    		G->arcs[j][i]= G->arcs[i][j]; /* 因为是无向图,矩阵对称 */
    	}
    }
    int main(void)
    {    
    	AMGraph G;    
    	createAMGraph(&G);
    	
    	return 0;
    }
    

    6.4.2 邻接表(Adjacency List)

    图的链式存储

    1、基本概念

    对于顶点V的 顶点单独放在一个链表——表头结点表。

    ​ 相邻顶点放在另一个链表——边表(相邻顶点表)。

    表头结点表

    ​ 数据域data ——存放顶点V的信息

    ​ 链域firstarc ——指向下一相邻顶点

    边表(相邻顶点表) :

    ​ 邻接点域adjvex ——与顶点V相邻的顶点V`在表头结点表下标位置

    ​ 信息域 info ——储存与边有关的信息,如权值等。

    ​ 链域 nextarc ——指向与V相邻的下一顶点

    2、存储

    三个结构体

    先创建边表,再创建表头结点表。

    #define MAX_INT 32767 //int在32位中能取得的最大值表示∞,64位中为 2,147,483,647
    #define MAX_VEX 100   //vertex最大顶点数
    typedef char vertexType; //顶点数据类型
    typedef int arcType      //边  权值类型
    /*边表(相邻顶点表)*/
    typedef struct arcNode{
        int adjvex;
        arcType info;
        struct arcNode *nextarc;
    }arcNode;
    /*表头顶点表*/
    typedef struct vertexNode{
        vertexType data;//顶点表
        arcNode *firstarc; // 边表类型的指针
    }vertexNode,AdjList[MAX_VEX];
    typedef struct {
        AdjList adjList;
        int vexNum,arcNum;
    }AdjGraph;
    

    3、创建无向图

    边表是单独创建

    arcNode *e;

    e=(arcNode *)malloc(sizeof(arcNode)); /* 向内存申请空间,生成边表结点 */

    createAdjList(AdjGraph *G){
        int i,j,k;
    	arcNode *e;
        /* 输入顶点数和边数 */
    	printf("输入顶点数和边数:\n");
    	scanf("%d,%d",&G->vexNum,&G->arcNum); 
    	for(i = 0;i < G->vexNum;i++) /* 读入顶点信息,建立顶点表 */
    	{
    		scanf(&G->adjList[i].data); 	/* 输入顶点信息 */
    		G->adjList[i].firstarc=NULL; 	/* 将边表置为空表 */
    	}
    	
    	
    	for(k = 0;k < G->arcNum;k++)/* 建立边表 */
    	{
    		printf("输入边(vi,vj)上的顶点序号:\n");
    		scanf("%d,%d",&i,&j); /* 输入边(vi,vj)上的顶点序号 */
    		e=(arcNode *)malloc(sizeof(arcNode)); /* 向内存申请空间,生成边表结点 */
    		e->adjvex=j;					/* 邻接序号为j */                         
    		e->next=G->adjList[i].firstarc;	/* 将e的指针指向当前顶点上指向的结点 */
    		G->adjList[i].firstarc=e;		/* 将当前顶点的指针指向e */               
    		
    		e=(arcNode *)malloc(sizeof(arcNode)); /* 向内存申请空间,生成边表结点 */
    		e->adjvex=i;					/* 邻接序号为i */                         
    		e->next=G->adjList[j].firstarc;	/* 将e的指针指向当前顶点上指向的结点 */
    		G->adjList[j].firstarc=e;		/* 将当前顶点的指针指向e */               
    	}
    }
    

    6.4.3 (有向图)十字链表

    6.4.4 (无向图)邻接多重表

    展开全文
  • 题意 : 给出两幅顶点数一样的图 G1、G2 ,现在要求在 G2 中选出一些集、使之构成一幅新的图 G ,要求 G 要 G1 同构,现在要你统计合法的 G 有多少种 分析 : 图的同构是离散数学里面图论的一个概念、具体的...

    题目链接

    题意 : 给出两幅顶点数一样的图 G1、G2 ,现在要求在 G2 中选出一些边集、使之构成一幅新的图 G ,要求 G 要与 G1 同构,现在要你统计合法的 G 有多少种

     

    分析 : 

    图的同构是离散数学里面图论的一个概念、具体的可以看 这里

    判断两幅图是否是同构的至今貌似还是 NP 问题

    由于顶点数最多只有 8、同时意味着边最多只有 28

    那么可以由此想到 O(n!) 枚举所有的顶点的双射 (实际就是枚举全排列)

    考察每个双射下两图是否能够构成同构关系

    判断是否构成双射只要考察其邻接矩阵是否能一样即可

    这就意味着去选出 G2 这副图中的某些边集

    使得当前枚举到的双射能够使得 G1 和 G2 同构

    由于边不多、所以可以状态压缩这些边集

    存到一个 set 中进行去重、最后 set 的大小即为答案

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    还有另外一种做法就是

    枚举双射计算出 G1 和 G2 同构方案数

    然后再计算出 G1 和 G1 自己的自同构方案数

    最后答案就是 ( G1 和 G2 同构方案数 ) / ( G1 和 G1 自己的自同构方案数 )

    说实话、这个东西、我并不是很理解...........

     

    #include<bits/stdc++.h>
    #define LL long long
    #define ULL unsigned long long
    
    #define scl(i) scanf("%lld", &i)
    #define scll(i, j) scanf("%lld %lld", &i, &j)
    #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
    #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l)
    
    #define scs(i) scanf("%s", i)
    #define sci(i) scanf("%d", &i)
    #define scd(i) scanf("%lf", &i)
    #define scIl(i) scanf("%I64d", &i)
    #define scii(i, j) scanf("%d %d", &i, &j)
    #define scdd(i, j) scanf("%lf %lf", &i, &j)
    #define scIll(i, j) scanf("%I64d %I64d", &i, &j)
    #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
    #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
    #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)
    #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l)
    #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l)
    #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l)
    
    #define lson l, m, rt<<1
    #define rson m+1, r, rt<<1|1
    #define lowbit(i) (i & (-i))
    #define mem(i, j) memset(i, j, sizeof(i))
    
    #define fir first
    #define sec second
    #define VI vector<int>
    #define ins(i) insert(i)
    #define pb(i) push_back(i)
    #define pii pair<int, int>
    #define mk(i, j) make_pair(i, j)
    #define all(i) i.begin(), i.end()
    #define pll pair<long long, long long>
    
    #define _TIME 0
    #define _INPUT 0
    #define _OUTPUT 0
    clock_t START, END;
    void __stTIME();
    void __enTIME();
    void __IOPUT();
    using namespace std;
    
    const int maxn = 8 + 5;
    
    int G1[maxn][maxn];
    int G2[maxn][maxn];
    
    map<pii, int> mp;
    set<LL> ans;
    
    int main(void){__stTIME();__IOPUT();
    
    
        int n, m1, m2;
    
        while(~sciii(n, m1, m2)){
    
            mem(G1, 0);
            mem(G2, 0);
            ans.clear();
            mp.clear();
    
            for(int i=0; i<m1; i++){
                int u, v;
                scii(u, v);
                G1[u][v] = G1[v][u] = 1;
            }
    
            for(int i=0; i<m2; i++){
                int u, v;
                scii(u, v);
                if(u < v) swap(u, v);
                mp[mk(u,v)] = i;
                G2[u][v] = G2[v][u] = 1;
            }
    
            int idx[maxn];
            for(int i=1; i<=n; i++) idx[i] = i;
    
            do{
                LL state = 0;
                bool ok = true;
                for(int i=1; i<=n; i++){///判断是否能构成同构
                    for(int j=1; j<=n; j++){
                        if(G1[i][j] && !G2[idx[i]][idx[j]]){///只考虑G1有边关联的两个顶点的情况
                            ok = false;
                            break;
                        }else{
                            if(G1[i][j]){
                                int u = idx[i];
                                int v = idx[j];
                                if(u < v) swap(u, v);
                                state |= (1LL<<mp[mk(u,v)]);///状态压缩
                            }
                        }
                    }
                    if(!ok) break;
                }
    
                if(!ok) continue;
    
                ans.ins(state);
    
            }while(next_permutation(idx+1, idx+1+n));
    
            printf("%d\n", (int)ans.size());
        }
    
    
    __enTIME();return 0;}
    
    
    void __stTIME()
    {
        #if _TIME
            START = clock();
        #endif
    }
    
    void __enTIME()
    {
        #if _TIME
            END = clock();
            cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl;
        #endif
    }
    
    void __IOPUT()
    {
        #if _INPUT
            freopen("in.txt", "r", stdin);
        #endif
        #if _OUTPUT
            freopen("out.txt", "w", stdout);
        #endif
    }
    View Code

     

    转载于:https://www.cnblogs.com/LiHior/p/9342440.html

    展开全文
  • 题目大意:一个含有n个顶点m条,求...解题思路:比赛的时候想的是,如果一个顶点不在环里,那它相连的就必定是一定要经过的,所有可以用拓扑排序把不在环上的顶点进行统计一下,每去一个顶点必定去掉...

    题目链接:https://ac.nowcoder.com/acm/contest/392/I

    题目大意:一个含有n个顶点m条边的图,求经过所有顶点必须要经过的边数。

    例:

    输入:

    5 5
    1 2
    2 3
    3 4
    4 5
    3 5

    输出:

    3

    解题思路:比赛的时候想的是,如果一个顶点不在环里,那与它相连的边就必定是一定要经过的边,所有可以用拓扑排序把不在环上的顶点进行统计一下,每去一个顶点必定去掉一条边,所以我们可以用总的边数减去不在环上的点的个数,不过这有个问题就是当有n个顶点,n-1条边的时候,产生的结果会是-1,开始没考虑这种情况WA了两发,我们只需要把答案和0取个最大值就好了。

    然后就是出的题解用的是tarjan,显然必要的边是割边,我们用总边数减去割边数就可以了。

    Tarjan做法:

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=300005;
    int n,m,head[maxn],par[maxn],dfn[maxn],low[maxn],tot,cnt,ans;
    struct node{
        int to,next;
    }edge[2*maxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void Tarjan(int u){
        dfn[u]=low[u]=++cnt;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(!dfn[v]){
                par[v]=u;
                Tarjan(v);
                if(low[v]>dfn[u]) ans++;
                low[u]=min(low[u],low[v]);
            }
            else if(v!=par[u]) low[u]=min(low[u],dfn[v]);
        }
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)head[i]=-1;
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        Tarjan(1);
        cout<<m-ans<<endl;
        return 0;
    }

    拓扑做法:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<string>
    #include<set>
    #include<cmath>
    #include<list>
    #include<deque>
    #include<cstdlib>
    #include<bitset>
    #include<stack>
    #include<map>
    #include<queue>
    using namespace std;
    typedef long long ll;
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    #define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
    const int INF=0x3f3f3f3f;
    const double PI=acos(-1.0);
    const double eps=1e-6;
    const ll mod=10007;
    const int maxn=1000005;
    ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
    const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    int n,m,in[100005],sum;
    vector<int> mp[100005];
    void topsort(){
        queue<int> que;
        for(int i=1;i<=n;i++){
            if(in[i]==1){
                que.push(i); sum++;
            }
        }
        while(que.size()){
            int u=que.front();
            que.pop();
            int size=mp[u].size();
            for(int i=0;i<size;i++){
                int v=mp[u][i];
                in[v]--;
                if(in[v]==1){
                    que.push(v);
                    sum++;
                }
            }
        }
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            mp[u].push_back(v);
            mp[v].push_back(u);
            in[u]++; in[v]++;
        }
        topsort();
        int ans=max(m-sum,0);
        cout<<ans<<endl;
        return 0;
    }

     

    转载于:https://www.cnblogs.com/zjl192628928/p/10517787.html

    展开全文
  • 题目大意:给出图的信息,...统计当前连通块的个数用 dfs方法和bfs方法都可以,常规问题不同的是要删除指定的顶点,也就是遍历到该节点时跳过即可。 AC代码: DFS: #include <iostream> #include <...
  • //图的顶点数和边数 } linkmap; int v[100]={0}; //深度优先遍历中标记已访问的信息 int dv[100]={0}; //广度优先遍历中标记已访问的信息 /*----------------定义建立图--------------*/ linkmap *create(linkmap *...
  • A1021 题目链接 个人思路 相较于个人思路来说,《算法笔记》思路略显复杂,甚至还涉及算法证明 此题存在一个矛盾点:统计每个节点深度与统计...首先,连通且边数为N-1(N为节点数)的图一定是树,本题给出 N-1行...
  • abc191

    2021-02-10 13:29:46
    多边形边数与顶点数相同,只需统计顶点数 对于每个点判断其是否为顶点即可 不是 是 不是 不存在 是 不是 对于每个格点,判断周围四个格子中黑格子个数是否为1或3即可 (由于题目保证黑格子连通和白格子连通,有一种...
  • 枚举角的顶点,然后再枚举该顶点引出的,可以用向量表示。对这些向量进行极角排序,枚举起始,用尺取的方法,算得成锐角,钝直角的的条统计,最后输出答案。 #include using namespace std; ...
  • 题目: 题解: 拓扑排序,207. 课程表代码一样的,只是将拓扑排序的顶点保留而已,注意的数组给的...3)删除入度为0的点,以及删除该点为起点的,并统计删除入度为0的顶点 4)若有向无环,则res.siz...
  • // 图的顶点的数目 int edgnum; // 图的的数目 VNode vexs[MAX]; }LGraph; /* * 返回ch在matrix矩阵中的位置 */ static int get_position(LGraph G, char ch) { int i; for(i=0; i; i++) if...
  • DataWhale组队Day5--前沿

    2021-01-26 01:19:45
    任务主题 作者关联(数据建模任务),对论文作者关系进行建模,统计最常出现作者关系; 构建作者关系,挖掘作者关系。...多重无向,即两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联。
  • 10.1 与数有关基本算法 10.1.1 基本数论一些事实 10.1.2 欧几里得GCD算法 10.1.3 模运算 10.1.4 模指数运算 10.1.5 模乘法逆元 10.1.6 素性测试 10.2 密码计算 10.2.1 对称加密模式 10.2.2 公钥密码系统 10.2.3 ...
  • 同学打包代码

    2012-06-22 13:48:26
    3、判断三角形种类(一般三角形、等腰三角形、等三角形、直角三角形和不能构成三角形); 4、计算并输出三角形面积 。 12、几何体表面积体积 一、定义一个抽象类形状(shape),包含输入基本图形...
  • 思路:我们发现如果是强连通,那么每一个顶点的出度入度必定不为0。所以我们可以将“缩点”,然后去统计出度或者入度为0点,取两者最大。(可以手推一遍) CODE: #include<iostream>#...
  • ACM算法模板和pku代码

    2010-11-09 16:15:16
    用最少点覆盖所有的边 DAG上记忆化树形DP,博弈 有限状态自动机+树形DP 状态压缩DP 炮兵阵地 Help Bob,买匹萨 匹配数量 堆筛子 全排列式状态DP 计算几何 多边形地图染色 数据结构 Hash 枚举+hash,方程解...
  • 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 拓扑排序 7.5 单源最短路径 7.6 最小代价生成树 7.7 全部最短路径 7.8 传递闭包 7.9 图的分解 7.9.1 双连通分支 7.9.2 强连通分支 7.9.3 利用...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。 注:1、要用面向对象的方法设计代码; 2、一个图是一个类的实例; 3、类...
  • 大话数据结构

    2018-12-14 16:02:18
    7.2.2图的顶点与边间关系 217 7.2.3连通图相关术语 219 7.2.4图的定义与术语总结 222 7.3图的抽象数据类型 222 7.4图的存储结构 223 因为美国的黑夜就是中国的白天,利用互联网,他的员工白天上班就可以监控到...
  • (16) 数据流用于抽象描述一个软件逻辑模型,数据流由一些特定图符构成。下列图符名标识图符不属于数据流合法图符是______。(A) A. 控制流 B. 加工 C. 数据存储 D. 源和潭 (17) 软件需求分析阶段工作...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
关键字:

统计图的顶点数与边数