编辑器加载中...
#define MAXNODE
typedef struct NODE
{
int num;
struct Node *next;
}Node;
typedef Node* Graph[MAXNODE];
//--------Build_Graph & Free_Graph-------------
Graph G,GT;
int nodenum,edgenum;
void Build_Graph(Graph &G,Graph >)
{
int nodeone,nodetwo;
Node *p;
memset(G,0,sizeof(G));
memset(GT,0,sizeof(GT));
for(int i=1;i<=edgenum;i++)
{
scanf("%d %d",&nodeone,&nodetwo);
p=(Node*)malloc(sizeof(Node));
p->num=nodetwo;
p->next=G[nodeone];
p=(Node*)malloc(sizeof(Node));
p->num=nodeone;
p->next=G[nodetwo];
}
}
void Free_Graph(Graph &G,Graph >)
{
Node *p,*next;
int i;
for(i=1;i<=nodenum;i++)
{
p=G[i];
while(p)
{
next=p->next;
free(p);
p=next;
}
p=GT[i];
while(p)
{
next=p->next;
free(p);
p=next;
}
}
}
//-------Kosaraju---------------
bool is_visited[MAXNODE];
int visit_order[MAXNODE];
int id_scc[MAXNODE];
void Fir_DFS(int i,int &order)
{
is_visited[i]=true;
for(Node *p=G[i];p;p=p->next)
{
int next=p->num;
if(false==is_visited[next])
Fir_DFS(next,order);
}
visit_order[++order]=i;
}
void Sec_DFS(int i,int id)
{
is_visited[i]=true;
for(Node *p=GT[i];p;p=p->next)
{
int next=p->num;
if(false==is_visited[next])
Sec_DFS(next,id);
}
id_scc[i]=id;
}
int Kosaraju()
{
int order=0;
memset(is_visited,false,sizeof(is_visited));
for(int i=1;i<=nodenum;i++)
{
if(false==is_visited[i])
Fir_DFS(i,order);
}
int cnt_scc=0;
memset(is_visited,false,sizeof(is_visited));
for(int i=nodenum;i>0;i--)
{
if(false==is_visited[visit_order[i]])
Sec_DFS(visit_order[i],++cnt_scc);
}
return cnt_scc;
}