#include <iostream>#include <vector>using namespace std;//有向图十字链表表示#define MAX_VERTEX_NUM 20typedef struct ArcBox{    int tailvex, headvex; //该弧尾和头顶点的位置    struct ArcBox *hlink, *tlink; //分别指向弧头相同和弧尾相同的弧的链域}ArcBox;typedef struct VexNode{    int data;    ArcBox *firstin, *firstout;//分别指向该顶点的第一条入弧和出弧}VexNode;typedef struct{    VexNode xlist[MAX_VERTEX_NUM]; //表头向量    int vexnum, arcnum; //有向图的顶点数和弧数}OLGraph;//定位顶点在xlist中的位置int LocateVex(OLGraph G, int data){    for(int i = 0; i < G.vexnum; i++)    {        if(G.xlist[i].data =http://www.mamicode.com/= data)        {            return i;        }    }    cout << "error the vertex "<< data << " is not in the list"<<endl;    return -1;}//有向图十字链表创建void CreateDG(OLGraph &G){    cout << "please input the number of vertex, the number of arc:";    cin >> G.vexnum >> G.arcnum;    for(int i = 0; i < G.vexnum; i++)    {        cout << "please input vertex data:";        cin >> G.xlist[i].data;        G.xlist[i].firstin = NULL;  //初始化指针        G.xlist[i].firstout = NULL;    }    for(int k = 0; k < G.arcnum; k++)    {        int v1, v2; //弧的尾和头        cout << "please input the tail and head vertex of each tail:";        cin >> v1 >> v2;        int i = LocateVex(G, v1);        int j = LocateVex(G, v2);        ArcBox * p = new ArcBox;        p->headvex = j;        p->tailvex = i;        p->hlink = G.xlist[j].firstin;        p->tlink = G.xlist[i].firstout;        G.xlist[j].firstin = p;        G.xlist[i].firstout = p;    }}//单向深度优先搜索//输入: 图G, 开始遍历点v, 遍历标志visited, 遍历方向dir 0 表示从尾向头遍历 1表示从头到尾遍历, vecor存放跳出遍历的顺序void DFS(OLGraph G, int v, int * visited, int dir, vector<int> * vec){    visited[v] = 1;    (*vec).push_back(v);    if(dir == 0) //从尾向头遍历    {        ArcBox * w = G.xlist[v].firstout;        while(w != NULL ) //注意 这里的while         {            if(visited[w->headvex] == 1)            {                w = w->tlink;            }            else//未访问过该点 递归遍历该点            {                DFS(G, w->headvex, visited, dir, vec);                w = w->tlink;            }        }    }    else //从头向尾遍历    {        ArcBox * w = G.xlist[v].firstin;        while(w != NULL)//查找下一个遍历点        {            if((visited[w->tailvex]) == 1)            {                w = w->hlink;            }            else//未访问过该点 递归遍历该点            {                DFS(G, w->tailvex, visited, dir, vec);                w = w->hlink;            }        }                    }}//查找有向图强连通分量vector<vector<int>> FindConnectedPart(OLGraph G){    vector<vector<int>> ConnectedPart;    vector<vector<int>> finished;    int* visited = new int[G.vexnum];    memset(visited, 0, G.vexnum * sizeof(int)); //初始化为全部没有访问过    //从尾向头遍历    for(int v = 0; v < G.vexnum; v++)    {        if(visited[v] == 0) //没有被访问过        {            vector<int> vec;            DFS(G, v, visited, 0, &vec);            finished.push_back(vec);        }    }    //从头向尾遍历    memset(visited, 0, G.vexnum * sizeof(int));     vector<int>::iterator it;    vector<vector<int>>::iterator it2;    int* find = new int[G.vexnum]; //find标识顶点实际上是否被查找过    for(int i = 0; i < G.vexnum; i++)     {        find[i] = 0;        visited[i] = 1;    }    for(it2 = finished.begin(); it2 < finished.end(); it2++)    {        //已经遍历过的部分visited不变，即都是1； find[i]= 0的表示本次遍历时不遍历结点i,为了跳过i，设它们的visited[i]=1; 但实际上，它们还没有被访问到        //比如从尾到头遍历时得到两个分量 （1,2,3,4）（5）        //那么为了找到重连通分量，从头到尾遍历4,3,2,1时不应该经过5 即可能从头到尾遍历时的分量是（1 2 3 5）（4）        // 但实际上重连通分量为(1,2,3)(4)(5)三个        for(it = it2->begin(); it < it2->end(); it++)        {            visited[*it] = 0; //只把本次遍历考虑到的顶点的visited设为0，其他为1，就不会加人遍历了            find[*it] = 1;        }        for(it = it2->begin(); it < it2->end(); it++)        {            if(visited[*it] == 0) //没有被访问过            {                vector<int> vec;                DFS(G, *it, visited, 1, &vec);                ConnectedPart.push_back(vec);            }        }    }    //输出重连通分量    int n = 0;    cout << "重连通分量有：" << endl;    for(it2 = ConnectedPart.begin(); it2 < ConnectedPart.end(); it2++)    {        cout << ++n << ":";        for(it = it2->begin(); it < it2->end(); it++)        {            cout << G.xlist[*it].data << " ";        }        cout<< endl;    }    delete [] visited;    delete [] find;    return ConnectedPart;}int main(){    OLGraph G;    CreateDG(G);    FindConnectedPart(G);    return 0;}