510 Retele

[•DITzoneC]

Aici puteţi discuta despre problema Retele.

[•toni2007]

imi poate da cineva care a facut de 100 problema un test mai mare? ca nu ma prind unde busesc (merge pe toate testele pe care le-am dat)

[•fireatmyself]

Cod:

123 456
1 2
1 2
1 2
1 3
2 3
3 4
3 2
3 4
3 4
3 5
4 5
5 3
4 5
4 5
5 6
6 1
7 8
8 7
9 10
9 16
10 1
10 9
11 115
11 115
11 115
11 115
11 115
11 115
11 115
12 13
13 112
13 21
14 123
14 123
14 123
14 123
15 104
16 19
17 33
18 17
19 14
20 18
21 20
22 15
23 22
24 23
25 24
26 75
27 35
28 25
29 28
30 29
31 30
32 31
33 27
33 34
33 34
34 27
34 35
35 12
35 36
36 37
37 38
38 26
38 39
39 40
40 41
41 42
42 36
42 43
42 51
43 44
44 45
45 46
46 47
47 48
48 49
48 50
49 50
50 51
51 50
51 50
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
51 52
52 51
52 51
52 51
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
52 53
54 53
54 53
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
53 54
54 55
54 55
54 55
54 55
54 55
54 55
54 55
54 55
54 55
55 56
56 57
56 57
56 57
56 57
56 57
56 57
56 57
56 57
56 57
56 59
57 58
57 58
57 58
57 58
57 58
57 58
58 59
58 59
58 59
58 59
58 59
58 59
58 59
59 60
59 60
59 60
59 60
59 64
59 64
59 64
59 64
59 64
59 64
59 64
59 64
59 64
60 61
60 61
60 61
60 61
60 61
60 61
60 61
60 61
60 61
61 62
62 63
63 64
64 65
64 66
65 66
66 67
66 72
67 68
67 68
68 69
69 70
70 71
71 72
72 73
72 73
73 74
73 74
73 74
73 74
73 74
74 42
74 75
75 76
75 76
76 77
76 77
77 78
77 78
77 78
77 78
77 78
77 78
78 79
78 79
78 79
78 79
78 79
78 79
78 79
78 79
78 79
78 79
79 80
79 80
79 80
79 80
79 80
79 80
79 80
79 80
79 80
79 80
80 19
80 19
80 19
80 19
80 19
80 81
80 81
80 81
80 81
80 81
80 82
80 82
80 82
80 82
80 82
81 82
81 82
81 82
81 82
81 82
82 83
82 83
82 83
82 83
82 83
82 84
82 84
82 84
82 84
82 84
83 84
83 84
83 84
83 84
83 84
84 85
84 85
84 85
84 85
84 85
84 86
84 86
84 86
84 86
84 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
85 86
86 87
86 87
86 87
86 87
86 87
86 88
86 88
86 88
86 88
86 88
87 88
87 88
87 88
87 88
87 88
88 89
88 89
88 89
88 89
88 89
88 90
88 90
88 90
88 90
88 90
89 90
89 90
89 90
89 90
89 90
90 91
90 91
90 91
90 91
90 91
90 92
90 92
90 92
90 92
90 92
91 22
91 92
92 26
92 93
93 14
93 94
94 95
95 96
96 97
97 98
98 99
99 100
100 93
100 93
100 93
100 93
100 93
100 93
100 93
101 13
102 32
103 102
104 103
105 119
106 105
107 101 
108 107
109 108
110 109
111 106
112 110
114 118
115 116
115 117
116 117
117 118
117 120
118 119
118 122
118 122
118 122
118 122
118 122
118 122
118 122
118 122
119 114
119 120
119 33
120 11
120 121
121 122
122 123
122 123
123 10
123 10
123 10
123 10
123 121
123 121
123 121
123 121
123 121

si raspunsul:

Cod:

13
6 1 2 3 4 5 6 
2 7 8 
8 9 10 14 16 19 121 122 123 
8 11 114 115 116 117 118 119 120 
16 12 13 17 18 20 21 27 33 34 35 101 107 108 109 110 112 
39 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 
19 26 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 
13 15 22 23 24 25 28 29 30 31 32 102 103 104 
8 93 94 95 96 97 98 99 100 
1 105 
1 106 
1 111 
1 113 

[•toni2007]

nu e bine testul de intrare: n este 123 si apare un element cu 124 (de fapt mai multe) si imi da kbs 11 la mine

[•fireatmyself]

 
scuze. vezi acum.

[•toni2007]

imi da

Cod:

9
6 1 2 3 4 5 6 
2 7 8 
8 9 10 14 16 19 121 122 123 
90 11 12 13 17 18 20 21 26 27 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 107 108 109 110 112 114 115 116 117 118 119 120 
13 15 22 23 24 25 28 29 30 31 32 102 103 104 
1 105 
1 106 
1 111 
1 113 

da vezi ca la tine 113 parca nu apare



Eu fac cam asa ca sa aflu numarul componentelor tare-conexe:

pentru fiecare nod  x nevizitat marchez cu plus toate nodurile in care pot ajunge din nodul x si cu minus toate nodurile din care se poate ajunge in x si apoi elimin toate nodurile marcate si cu plus si cu minus si continui cu urmatorul nod nevizitat

[•fireatmyself]

nu stiu daca este suficient (nu gasesc acum un contraexemplu), dar sigur iese din timp. incearca sa gasesti un algoritm O(V+E).

HINT:foloseste doua df-uri, unul pentru graful normal si celalat pentru graful transpus (inversat). cand faci al doilea df, trebuie sa parcurgi nodurile intr-o anumita ordine (pe care o determini cu primul df).

[•DraStiK]

De curand am aflat si eu ca STL e foarte tare  si m-am gandit sa folosesc containerul SET din STL pentru a-mi retine elementele unei componente conexe in ordine crescatoare. Problema este ca nu stiu cum sa sortez SET-urile in functie de primul element.

am asa:
set <int> rez[MaxN];

Ma poate ajuta cineva?

[•devilkind]

ai incercat sort(S + 1, S + K + 1) ? (K e numarul de seturi)

STL intradevar e super tare si stie sa compare si seturi . Cauta prima pozitie pe care elementele din set-uri difera si le compara.

[•DraStiK]

Multumesc mult devilkind. A mers.

[•S7012MY]

Se poate sa iau 0 puncte din cauza ca pe exemplu in loc sa afisez ca si mai sus afisez asa:
4
3 1 7 9
2 2 3
1 8
4 4 5 6 10
edit: scz n-am citit atent 

[•pauldb]

Da:

Retelele vor fi afisate in ordinea crescatoare a abonatului de numar minim, iar abonatii din aceeasi retea vor fi, de asemenea, afisati in ordine crescatoare.

[•bugy]

cum as putea sa optimizez sortarile.?...  nu stiu stl

[•pauldb]

Incearca sa inveti. Nu trebuie sa stii tot STL-ul, dar sort-ul e o chestiune foarte utila. In mare trebuie sa folosesti urmatorul cod:

Cod:

#include <algorithm>

using namespace std;

... 

sort(A+start, A+end); // sortezi numerele din intervalul [start, end) din vectorul A

Pentru sortari dupa criterii mai complexe, poti sa cauta pe forum, exista mai multe topic-uri pe tema asta deja.

[•bugy]

multumesc paul

[•rares192]

Cum pot sa folosesc sort din STL ca sa sortez liniile dupa primul element un vector<vector<int> > sol ?
Initial am sortat cu sort( sol[i ].begin(), sol[i ].end(), cmp); si acuma ca am elementele de pe linii sortate si vreau sa sortez dupa primul element liniile ..am incercat sort( sol.begin(), sol.end(), cmp) si nu merge..   cum as putea face ?

[Editat de admin] Cand scrii "[i ]" e bine sa pui un spatiu deoarece forumu considera ca vrei ca de acolo sa scrii text italic.

[•CosminRusu]

In legatura cu postul lui Dragos Oprica (stiu ca a trecut ceva vreme).
Pentru cei care folosesc set pentru a avea nodurile dintr-o componenta conexa in ordine crescatoare, iar mai apoi si aceste seturi ordonate tot crescator, cel mai bine este sa folositi stl pana la capat astfel :

Cod:

set < set < int > > ctc

[•ionut98]

Imi explica cineva de ce nu e corecta afisare:

3
3 1 7 9
2 2 3
5 4 5 6 8 10

sau

4
3 1 7 9
3 2 3 4
3 5 6 10
1 8

[•tudorgalatan]

Îmi poate spune cineva ce este greșit în acest cod?

Cod:

#include <fstream>
#include <vector>

using namespace std;

void DFS1 (unsigned int k);
void DFS2 (unsigned int k);

unsigned short int N;
unsigned int M;
unsigned short int x, y;

vector <unsigned int> v1[50001], v2[50001];
bool seen[50001];
unsigned int vec[50001];
unsigned int i, j, w;

vector <unsigned int> sol[50001];
unsigned int T;

int main ()
{
    ifstream fin ("retele.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    fin.close();
    for (i=1; i<=N; i++)
        if (!seen[i])
            DFS1(i);
    for (i=N; i>=1; i--)
        if (seen[vec[i]])
        {
            T++;
            DFS2(vec[i]);
        }
    ofstream fout ("retele.out");
    fout << T << '\n';
    for (i=1; i<=T; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
    fout.close();
    return 0;
}

void DFS1 (unsigned int k)
{
    unsigned int i;
    seen[k] = 1;
    for (i=0; i<v1[k].size(); i++)
        if (!seen[v1[k][i]])
            DFS1(v1[k][i]);
    w++;
    vec[w] = k;
}

void DFS2 (unsigned int k)
{
    unsigned int i;
    seen[k] = 0;
    sol[T].push_back(k);
    for (i=0; i<v2[k].size(); i++)
        if (seen[v2[k][i]])
            DFS2(v2[k][i]);
}

[•tudorgalatan]

OUTPUT:

Cod:

4
4 5 10 6 
8 
2 3 
1 7 9 

[•tudorgalatan]

"Retelele vor fi afisate in ordinea crescatoare a abonatului de numar minim.".

Mai exact, problema mea este cum fac asta.