有向图的弱连通分支,用的是强连通分支+缩点。
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 1005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int flag; //强连通分支标号
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct HEAD //结点头
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int state; //搜索处在的状态
int number; //强连通分支的结点个数
int flag; //强连通分支标号
int count; //结点的入度
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int next;
int last;
};
HEAD head1[LEN]; //原图
HEAD head2[LEN]; //逆图
HEAD head3[LEN]; //缩点后的图
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int time[LEN]; //存储结点
int next_time;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct //模拟的内存
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int num;
int next;
}node[LEN*24];
int next_node;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init () //初始化
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
flag = 0;
next_node = 0;
next_time = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init_head ( int n, HEAD *head ) //初始化链表
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[i].count = 0;
head[i].flag = -1;
head[i].next = -1;
head[i].number = 0;
head[i].state = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void ins ( int a, int b, HEAD *head ) //插入一条边
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
node[next_node].next = -1;
node[next_node].num = b;
next_node ++;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( head[a].next==-1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[a].next = next_node-1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
node[ head[a].last ].next = next_node-1;
}
head[a].last = next_node-1;
head[b].count ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//极度简化的堆栈
int stack[LEN][2];
int top;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline void push( int a[] ) //出堆栈
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
top ++;
stack[top][0] = a[0];
stack[top][1] = a[1];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline int isempty ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return top<0 ? 1:0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void mark ( int s, HEAD *head ) //对原图进行深搜
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
int now[2];
top = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
now[0] = s;
now[1] = head[s].next;
push ( now );
head[ now[0] ].state = 1;
while ( !isempty () )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
now[0] = stack[top][0];
now[1] = stack[top][1];
for ( i=now[1]; i!=-1; i=node[i].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( !head[ node[i].num ].state )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[top][1] = node[i].next;
now[0] = node[i].num;
now[1] = head[ node[i].num ].next;
push ( now );
head[ now[0] ].state = 1;
break;
}
}
if ( i==-1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[ now[0] ].state = 2;
time[ next_time++ ] = now[0];
top --;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void ser ( int s, HEAD *head ) //对逆图进行深搜
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
int now[2];
top = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
now[0] = s;
now[1] = head[s].next;
push ( now );
head[ now[0] ].state = 1;
head[ now[0] ].flag = flag;
while ( !isempty () )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
now[0] = stack[top][0];
now[1] = stack[top][1];
for ( i=now[1]; i!=-1; i=node[i].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( !head[ node[i].num ].state )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
stack[top][1] = node[i].next;
now[0] = node[i].num;
now[1] = head[ node[i].num ].next;
push ( now );
head[ now[0] ].flag = flag;
head[ now[0] ].state = 1;
break;
}
}
if ( i==-1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[ now[0] ].state = 2;
top --;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//拓扑排序
int queue[LEN][2]; //队列
int tou, tail; //队列游标
int used[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline void inq ( int a[] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tail ++;
queue[tail][0] = a[0];
queue[tail][1] = a[1];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline void outq ( int a[] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
a[0] = queue[tail][0];
a[1] = queue[tail][1];
tou ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
inline int empty ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return tou>tail ? 1:0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int bfs ( int n, HEAD *head )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int max = -1;
int in[2];
int out[2];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tou = 0, tail = -1;
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
used[i] = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( !head[i].count )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
in[0] = i;
in[1] = 0;
inq ( in );
used[ in[0] ] = 1;
}
}
while ( !empty () )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
outq ( out );
if ( max<out[1] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
max = out[1];
}
for ( int i=head[ out[0] ].next; i!=-1; i=node[i].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[ node[i].num ].count --;
if ( !head[ node[i].num ].count )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
in[0] = node[i].num;
in[1] = out[1] + 1;
inq ( in );
used[ in[0] ] = 1;
}
}
}
return max;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int work ( int n, HEAD *h1, HEAD *h2, HEAD *h3 ) //主要工作函数
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( !h1[i].state )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mark ( i, h1 );
}
}
for ( int i=next_time-1; i>=0; i-- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( !h2[ time[i] ].state )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ser ( time[i], h2 );
flag ++;
}
}
//找极大强连通分支
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
init_head ( flag, h3 );
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int j=h2[i].next; j!=-1; j=node[j].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( h2[i].flag!=h2[ node[j].num ].flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ins ( h2[ node[j].num ].flag, h2[i].flag, h3 );
}
}
h3[ h2[i].flag ].number ++;
}
//缩点
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( bfs ( flag, h3 )==flag-1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 1;
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t;
scanf ( "%d", &t );
while ( t -- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
init ();
int n, m;
int a, b;
scanf ( "%d%d", &n, &m );
init_head ( n, head1 );
init_head ( n, head2 );
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d", &a, &b );
if ( a!=b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ins ( a-1, b-1, head1 );
ins ( b-1, a-1, head2 );
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ans = work ( n, head1, head2, head3 );
if ( ans )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "Yes\n" );
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "No\n" );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|