This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 森を木の vector に分解する (無向) O(|V|)
// ・まだチェックしていない頂点に関して、その頂点から BFS を行う
// ・頂点番号を振り直しながら辺を張っていく
template <typename T>
using Graph = vector< vector< Edge<T> > >;
template <typename T>
Graph<T> Forest2Trees(Graph<T> &G) {
int n = (int)G.size();
vector<int> vtxid(n, -1);
vector< Graph<T> > ret;
for(int i=0; i<n; i++) {
if(vtxid[i] >= 0) continue;
Graph<T> Tree(1);
int cur = 0;
vtxid[i] = cur++;
queue<int> q; q.push(i);
while(!q.empty()) {
int k = q.front(); q.pop();
for(size_t x=0; x<G[k].size(); x++) {
int to = G[k][x].to; T cost = G[k][x].cost;
if(vtxid[to] >= 0) continue;
vtxid[to] = cur++;
Tree.push_back(vector< Edge<T> >());
Tree[ vtxid[k ] ].push_back( Edge<T>(vtxid[to], cost) );
Tree[ vtxid[to] ].push_back( Edge<T>(vtxid[k ], cost) );
q.push(to);
}
}
ret.push_back(Tree);
}
return ret;
}
#line 1 "graph/graph_015_forest2trees.cpp"
// 森を木の vector に分解する (無向) O(|V|)
// ・まだチェックしていない頂点に関して、その頂点から BFS を行う
// ・頂点番号を振り直しながら辺を張っていく
template <typename T>
using Graph = vector< vector< Edge<T> > >;
template <typename T>
Graph<T> Forest2Trees(Graph<T> &G) {
int n = (int)G.size();
vector<int> vtxid(n, -1);
vector< Graph<T> > ret;
for(int i=0; i<n; i++) {
if(vtxid[i] >= 0) continue;
Graph<T> Tree(1);
int cur = 0;
vtxid[i] = cur++;
queue<int> q; q.push(i);
while(!q.empty()) {
int k = q.front(); q.pop();
for(size_t x=0; x<G[k].size(); x++) {
int to = G[k][x].to; T cost = G[k][x].cost;
if(vtxid[to] >= 0) continue;
vtxid[to] = cur++;
Tree.push_back(vector< Edge<T> >());
Tree[ vtxid[k ] ].push_back( Edge<T>(vtxid[to], cost) );
Tree[ vtxid[to] ].push_back( Edge<T>(vtxid[k ], cost) );
q.push(to);
}
}
ret.push_back(Tree);
}
return ret;
}