IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Точки сочленения графа
Triplet
сообщение 13.12.2008 21:43
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 78
Пол: Женский

Репутация: -  0  +


Помогите, пожалуйста, решить задачу.
Вершина графа называется точкой сочленения, если её удаление приводит к увеличению количества компонент связности. Найдите все точки сочленения заданного графа.

Есть вот такой код:
program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

const maxn = 100000;
maxm = 100000;

var i,j,k,n,m : longint;
u,v,next : array [1..2*maxm] of longint;
g,num : array [1..maxn] of longint;
vis : array [1..maxn] of boolean;

procedure Add(i : longint);
begin
next[i] := g[u[i]]; g[u[i]] := i;
end;

function Dfs(x,fr : longint) : longint;
var i,j,t,min : longint;
f : boolean;


begin
inc(k); num[x] := k; vis[x] := true; min := k;
f := false; t := 0; i := g[x];
while i <> 0 do begin
if not vis[v[i]] then begin
j := Dfs(v[i],x); inc(t);
if j < min then min := j;
if j >= num[x] then f := true;
end else if (v[i] <> fr) and (num[v[i]] < min) then min := num[v[i]];

i := next[i];
end;
if fr = 0 then begin
if t > 1 then writeln(x);
end else if f then writeln(x);
Dfs := min;

end;

begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n,m);
fillchar(g,sizeof(g),0);
for i := 1 to m do begin
read(u[i],v[i]); Add(i);
u[m+i] := v[i]; v[m+i] := u[i]; Add(m+i);
end;
fillchar(vis,sizeof(vis),false);
k := 0; Dfs(1,0);
close(input); close(output);
end.

Но в output не получается правильного ответа.
Помогите, пожалуйста, найти ошибку.
Заранее огромное спасибо!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 20.07.2025 14:20
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"