有向图的弱连通分支,用的是强连通分支+缩点。
#include <stdio.h>

const int LEN = 1005;

int flag; //强连通分支标号

struct HEAD //结点头
  {
int state; //搜索处在的状态
int number; //强连通分支的结点个数
int flag; //强连通分支标号
int count; //结点的入度

int next;
int last;
};
HEAD head1[LEN]; //原图
HEAD head2[LEN]; //逆图
HEAD head3[LEN]; //缩点后的图

int time[LEN]; //存储结点
int next_time;

struct //模拟的内存
  {
int num;
int next;
}node[LEN*24];
int next_node;

void init () //初始化
  {

flag = 0;
next_node = 0;
next_time = 0;
}

void init_head ( int n, HEAD *head ) //初始化链表
  {

for ( int i=0; i<n; i++ )
 {
head[i].count = 0;
head[i].flag = -1;
head[i].next = -1;
head[i].number = 0;
head[i].state = 0;
}
}

void ins ( int a, int b, HEAD *head ) //插入一条边
  {

node[next_node].next = -1;
node[next_node].num = b;
next_node ++;

if ( head[a].next==-1 )
 {
head[a].next = next_node-1;
}
else
 {
node[ head[a].last ].next = next_node-1;
}
head[a].last = next_node-1;
head[b].count ++;
}

//极度简化的堆栈
int stack[LEN][2];
int top;

inline void push( int a[] ) //出堆栈
  {

top ++;
stack[top][0] = a[0];
stack[top][1] = a[1];
}

inline int isempty ()
  {

return top<0 ? 1:0;
}

void mark ( int s, HEAD *head ) //对原图进行深搜
  {

int i;
int now[2];
top = -1;

now[0] = s;
now[1] = head[s].next;
push ( now );
head[ now[0] ].state = 1;
while ( !isempty () )
 {
now[0] = stack[top][0];
now[1] = stack[top][1];
for ( i=now[1]; i!=-1; i=node[i].next )
 {
if ( !head[ node[i].num ].state )
 {
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 )
 {
head[ now[0] ].state = 2;
time[ next_time++ ] = now[0];
top --;
}
}
}

void ser ( int s, HEAD *head ) //对逆图进行深搜
  {

int i;
int now[2];
top = -1;

now[0] = s;
now[1] = head[s].next;
push ( now );
head[ now[0] ].state = 1;
head[ now[0] ].flag = flag;
while ( !isempty () )
 {
now[0] = stack[top][0];
now[1] = stack[top][1];
for ( i=now[1]; i!=-1; i=node[i].next )
 {
if ( !head[ node[i].num ].state )
 {
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 )
 {
head[ now[0] ].state = 2;
top --;
}
}
}

//拓扑排序
int queue[LEN][2]; //队列
int tou, tail; //队列游标
int used[LEN];

inline void inq ( int a[] )
  {

tail ++;
queue[tail][0] = a[0];
queue[tail][1] = a[1];
}

inline void outq ( int a[] )
  {

a[0] = queue[tail][0];
a[1] = queue[tail][1];
tou ++;
}

inline int empty ()
  {

return tou>tail ? 1:0;
}

int bfs ( int n, HEAD *head )
  {

int max = -1;
int in[2];
int out[2];

tou = 0, tail = -1;
for ( int i=0; i<n; i++ )
 {
used[i] = 0;
}

for ( int i=0; i<n; i++ )
 {
if ( !head[i].count )
 {
in[0] = i;
in[1] = 0;
inq ( in );
used[ in[0] ] = 1;
}
}
while ( !empty () )
 {
outq ( out );
if ( max<out[1] )
 {
max = out[1];
}
for ( int i=head[ out[0] ].next; i!=-1; i=node[i].next )
 {
head[ node[i].num ].count --;
if ( !head[ node[i].num ].count )
 {
in[0] = node[i].num;
in[1] = out[1] + 1;
inq ( in );
used[ in[0] ] = 1;
}
}
}
return max;
}

int work ( int n, HEAD *h1, HEAD *h2, HEAD *h3 ) //主要工作函数
  {

for ( int i=0; i<n; i++ )
 {
if ( !h1[i].state )
 {
mark ( i, h1 );
}
}
for ( int i=next_time-1; i>=0; i-- )
 {
if ( !h2[ time[i] ].state )
 {
ser ( time[i], h2 );
flag ++;
}
}
//找极大强连通分支

init_head ( flag, h3 );
for ( int i=0; i<n; i++ )
 {
for ( int j=h2[i].next; j!=-1; j=node[j].next )
 {
if ( h2[i].flag!=h2[ node[j].num ].flag )
 {
ins ( h2[ node[j].num ].flag, h2[i].flag, h3 );
}
}
h3[ h2[i].flag ].number ++;
}
//缩点

if ( bfs ( flag, h3 )==flag-1 )
 {
return 1;
}
return 0;
}

int main ()
  {

int t;
scanf ( "%d", &t );
while ( t -- )
 {
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++ )
 {
scanf ( "%d%d", &a, &b );
if ( a!=b )
 {
ins ( a-1, b-1, head1 );
ins ( b-1, a-1, head2 );
}
}

int ans = work ( n, head1, head2, head3 );
if ( ans )
 {
printf ( "Yes\n" );
}
else
 {
printf ( "No\n" );
}
}
return 0;
}

|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 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 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|