Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int nmax=2e3+10;
- vector<int> G[nmax];
- int low[nmax];
- bool vis[nmax];
- int pom=2;
- int preorder[nmax];
- int licznik=1;
- int dwuspojna[nmax];
- void dfs(int x,int ojciec)
- {
- //cout<<x<<" ";
- vis[x]=true;
- preorder[x]=licznik;
- low[x]=licznik;
- licznik++;
- for(int i=0;i<G[x].size();i++)
- {
- int a=G[x][i];
- if(a!=ojciec)
- {
- if(vis[a])
- low[x]=min(low[x],preorder[a]);
- else
- {
- dfs(a,x);
- low[x]=min(low[x],low[a]);
- }
- }
- }
- }
- void kladz(int x)
- {
- vis[x]=true;
- for(int i=0;i<G[x].size();i++)
- {
- int a=G[x][i];
- if(!vis[a])
- {
- if(low[a]==preorder[a])
- {
- dwuspojna[a]=pom;
- pom++;
- }
- else
- {
- dwuspojna[a]=dwuspojna[x];
- }
- kladz(a);
- }
- }
- }
- int main()
- {
- int n;
- cin>>n;
- for(int i=2;i<=n;i++)
- {
- for(int j=1;j<i;j++)
- {
- int a;
- cin>>a;
- if(a)
- {
- G[j].push_back(i);
- }
- else
- {
- G[i].push_back(j);
- }
- }
- }
- dfs(1,0);
- for(int i=1;i<=n;i++)
- {
- for(int j=0;j<G[i].size();j++)
- {
- cout<<G[i][j]<<" ";
- }
- cout<<"\n";
- }
- cout<<"\n";
- for(int i=1;i<=n;i++)
- cout<<preorder[i]<<" "<<low[i]<<"\n";
- fill(vis,vis+nmax,0);
- dwuspojna[1]=1;
- kladz(1);
- cout<<"\n";
- for(int i=1;i<=n;i++)
- cout<<dwuspojna[i]<<" ";
- }
- /*
- 8
- 1
- 1 1
- 1 0 1
- 1 1 1 1
- 1 1 1 1 1
- 1 1 1 1 0 1
- 1 1 1 1 0 1 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement