连通分支
#include <stdio.h>

const int LEN = 10005;

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

struct HEAD //结点头
  {
int state; //搜索处在的状态
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*20];
int next_node;

int hash[LEN];

void init ( int n ) //初始化
  {

for ( int i=0; i<n; i++ )
 {
hash[i] = 0;
}
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].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[a].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 --;
}
}
}

void 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 );
}
}
}
//缩点

for ( int i=0; i<flag; i++ )
 {
if ( !h3[i].count )
 {
for ( int j=0; j<n; j++ )
 {
if ( h2[j].flag==i )
 {
hash[j] = 1;
}
}
}
}
for ( int i=0; i<n; i++ )
 {
if ( hash[i] )
 {
printf ( "%d ", i+1 );
}
}
printf ( "\n" );
}

int main ()
  {

int n, m;
int a, b;
while ( scanf ( "%d", &n )!=EOF && n )
 {
scanf ( "%d", &m );
init ( n );
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 );
}
}
work ( n, head1, head2, head3 );
}
return 0;
}


|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
24 | 25 | 26 | 27 | 28 | 29 | 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)
随笔档案
搜索
最新评论

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