/* Задача 1.1 ПРИЯТЕЛИ В един град има N жители, за някои двойки от които се знае, че са приятели. От известната максимата “Приятелите на моите приятели са и мои приятели” следва, че ако A и B са приятели и B и C са приятели, то A и C също са приятели. Да се направи програма FRIEND.EXE, която намира броя на хората в най-голямата група от приятели. Първият ред на стандартния вход съдържа числата N и M, където N е броят на жителите (10 <= N <= 30000), а M (0 <= M <= 500000) е броят на дадените двойки приятели. На всеки от следващите M реда има по две числа – номерата на двойка приятели A, B (1 <= A <= N, 1 <= B <= N, A != B), като между дадените двойки може да има и повтарящи се. На стандартния изход да се изведе едно число – максималният брой на хората в образуваните групи от приятели. РЕШЕНИЕ от Иван Анев Нека представим хората в задачата като върхове на граф, а приятелството като ребро между два върха. В така представения граф максимата “приятелите на моите приятели са и мои приятели”, може да се изкаже като - два върха са “приятели” ако съществува път между тях. Група от приятели е подмножество на върховете на графа, в което между всеки два върха има път и няма връх непринадлежащ на множеството, от който да има път към връх в множеството. Такова подмножество се нарича свързана компонента и ние може лесно да намерим свързаната компонента, към която пренадлежи някой връх като проверим кои са достижимите върхове от него. Последното става лесно, чрез търсене в дълбочина, като маркираме вече посетените върхове. Нашето решение ще представлява пряка реализация на горната идея. Ще построим граф, като го представим със списък на съседство, като за всеки връх пазим свързан списък от съседите му. После от всеки непосетен връх на графа, чрез търсене в дълбочина, обхождаме достижимите от него върхове, като броим техния брой и ги маркираме като посетени. При всяко търсене в дълбочина ние откриваме броя на върховете в поредната свързана компонента и отговора на задачата ни е най-големия такъв брой. */ /* NAME: Ivan Anev PROG: friend LANG: C */ #include <stdio.h> #include <stdlib.h> #define MAXN 32768 typedef struct Vex TVex; typedef struct Edge TEdge; struct Vex { int v; TEdge *edges; }; struct Edge { int v; TEdge *next; }; int n, m; TVex vs[MAXN]; TEdge *es; int ec; int csize, ans; void readf(void); void solve(void); void writef(void); int main(void) { readf(); solve(); writef(); return 0; } void readf(void) { int i, a, b; void add_edge(int a, int b); scanf("%d%d", &n, &m); es = (TEdge*)malloc(sizeof(TEdge) * 2 * m); for (i = 0; i < m; ++i) { scanf("%d%d", &a, &b); --a; --b; add_edge(a, b); add_edge(b, a); } } void solve(void) { int i; void dfs(int v); for (i = 0; i < n; ++i) if (vs[i].v == 0) { csize = 0; dfs(i); if (csize > ans) ans = csize; } } void writef(void) { printf("%d\n", ans); } void add_edge(int a, int b) { TEdge *ne; ne = &es[ec++]; ne->v = b; ne->next = vs[a].edges; vs[a].edges = ne; } void dfs(int v) { TEdge *e; ++csize; vs[v].v = 1; for (e = vs[v].edges; e; e = e->next) if (vs[e->v].v == 0) dfs(e->v); }