SHOW:
|
|
- or go back to the newest paste.
| 1 | //============================================================================ | |
| 2 | // Name : Graf.cpp | |
| 3 | // Author : Alexa Lukac | |
| 4 | // Version : | |
| 5 | // Copyright : | |
| 6 | // Description : Hello World in C++, Ansi-style | |
| 7 | //============================================================================ | |
| 8 | ||
| 9 | #include <iostream> | |
| 10 | using namespace std; | |
| 11 | ||
| 12 | int n,m; //n-broj cvorova, m-broj grana | |
| 13 | int time1=0; | |
| 14 | bool connected[6000][6000]; | |
| 15 | struct cvor | |
| 16 | {
| |
| 17 | cvor() : visited(false), disctime1(-1), endtime1(-1), low(-1) {}
| |
| 18 | bool visited; | |
| 19 | int disctime1; //vreme pronalaska | |
| 20 | int endtime1; //vreme zavrsetka sa ovim cvorom | |
| 21 | int low; //najvise sto mozemo da odemo | |
| 22 | }; | |
| 23 | cvor niz[5000]; | |
| 24 | ||
| 25 | void dfs(int a) | |
| 26 | - | for(int i=0;i<n && connected[a][i] && !niz[i].visited;i++) |
| 26 | + | |
| 27 | if(niz[a].visited==false) | |
| 28 | {
| |
| 29 | bool art=true; | |
| 30 | cvor &t=niz[a]; | |
| 31 | t.visited=true; | |
| 32 | t.low=t.disctime1=++time1; | |
| 33 | ||
| 34 | for(int i=0;i<n;i++) | |
| 35 | {
| |
| 36 | if(connected[a][i]&&!niz[i].visited){
| |
| 37 | art=false; | |
| 38 | bool most=true; | |
| 39 | dfs(i); | |
| 40 | if(niz[i].low>=t.disctime1) | |
| 41 | {
| |
| 42 | t.low=niz[i].low; | |
| 43 | most=false; | |
| 44 | }else | |
| 45 | {
| |
| 46 | art=true; | |
| 47 | } | |
| 48 | if(most) | |
| 49 | cout << endl << "Most: " << a << "-" << i; | |
| 50 | } | |
| 51 | } | |
| 52 | if(art) | |
| 53 | cout << endl << "Artikulacioni cvor: " << a; | |
| 54 | t.endtime1=++time1; | |
| 55 | } | |
| 56 | } | |
| 57 | ||
| 58 | int main() {
| |
| 59 | for(int i=0;i<5005;i++) | |
| 60 | for(int j=0;j<5005;j++) | |
| 61 | connected[i][j]=false; | |
| 62 | - | } |
| 62 | + | |
| 63 | cin >> n >> m; | |
| 64 | ||
| 65 | for(int i=0;i<m;i++) | |
| 66 | {
| |
| 67 | int a,b; | |
| 68 | cin >> a >> b; | |
| 69 | connected[a][b]=connected[b][a]=true; | |
| 70 | } | |
| 71 | return 0; | |
| 72 | } | |
| 73 | ||
| 74 | ||
| 75 | /* | |
| 76 | * 4 4 | |
| 77 | 0 1 | |
| 78 | 1 2 | |
| 79 | 1 3 | |
| 80 | 0 3 | |
| 81 | ||
| 82 | 9 10 | |
| 83 | 0 2 | |
| 84 | 2 5 | |
| 85 | 2 3 | |
| 86 | 3 1 | |
| 87 | 3 4 | |
| 88 | 4 7 | |
| 89 | 3 7 | |
| 90 | 5 6 | |
| 91 | 5 7 | |
| 92 | 7 8 | |
| 93 | ||
| 94 | * | |
| 95 | */ |
