166 lines
4.1 KiB
Rust
166 lines
4.1 KiB
Rust
use std::fmt;
|
|
|
|
macro_rules! parse_line {
|
|
($($t: ty),+) => ({
|
|
let mut line = String::new();
|
|
std::io::stdin().read_line(&mut line).unwrap();
|
|
let mut iter = line.split_whitespace();
|
|
($(iter.next().unwrap().parse::<$t>().unwrap()),+)
|
|
})
|
|
}
|
|
|
|
// Node
|
|
type NodeIndex = usize;
|
|
|
|
#[derive(Copy, Clone)]
|
|
struct NodeItem{
|
|
visited : bool,
|
|
first_edge : Option<EdgeIndex>,
|
|
}
|
|
|
|
impl NodeItem{
|
|
fn new() -> NodeItem{
|
|
NodeItem{
|
|
visited : false,
|
|
first_edge : None,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl fmt::Display for NodeItem{
|
|
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
|
|
match self.first_edge{
|
|
None => write!(f, "Visited : {}\nFirst Edge : None\n===========================\n",
|
|
self.visited),
|
|
Some(i) => write!(f, "Visited : {}\nFirst Edge : E{}\n===========================\n",
|
|
self.visited, i + 1),
|
|
}
|
|
}
|
|
}
|
|
|
|
// Edge
|
|
type EdgeIndex = usize;
|
|
|
|
#[derive(Copy, Clone)]
|
|
struct EdgeItem{
|
|
target : NodeIndex,
|
|
next_edge : Option<EdgeIndex>,
|
|
}
|
|
|
|
impl EdgeItem{
|
|
fn new(target: NodeIndex) -> EdgeItem{
|
|
EdgeItem{
|
|
target : target,
|
|
next_edge : None,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl fmt::Display for EdgeItem{
|
|
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
|
|
match self.next_edge{
|
|
None => write!(f, "Target : N{}\nNext Edge : None\n===========================\n",
|
|
self.target + 1),
|
|
Some(i) => write!(f, "Target : N{}\nNext Edge : E{}\n===========================\n",
|
|
self.target + 1, i + 1),
|
|
}
|
|
}
|
|
}
|
|
|
|
// Graph
|
|
struct Graph{
|
|
nodes: Vec::<NodeItem>,
|
|
edges: Vec::<EdgeItem>,
|
|
}
|
|
|
|
impl Graph{
|
|
fn new(num_nodes: NodeIndex, num_edges: EdgeIndex) -> Graph{
|
|
let mut graph = Graph{
|
|
nodes : Vec::with_capacity(num_nodes),
|
|
edges : Vec::with_capacity(2 * num_edges),
|
|
};
|
|
|
|
for _i in 0..num_nodes{
|
|
graph.nodes.push(NodeItem::new());
|
|
}
|
|
|
|
return graph;
|
|
}
|
|
|
|
fn add_edge(&mut self, source: NodeIndex, target: NodeIndex){
|
|
let edge_index = self.edges.len();
|
|
self.edges.push(EdgeItem::new(target));
|
|
|
|
if let Some(idx) = self.nodes[source].first_edge{
|
|
self.edges[edge_index].next_edge = Some(idx);
|
|
}
|
|
self.nodes[source].first_edge = Some(edge_index);
|
|
}
|
|
|
|
fn clear(&mut self){
|
|
for mut node in self.nodes.iter_mut(){
|
|
node.visited = false;
|
|
}
|
|
}
|
|
|
|
fn dfs(&mut self, start: NodeIndex) -> usize{
|
|
return self.dfs_backtrack(start) - 1;
|
|
}
|
|
|
|
fn dfs_backtrack(&mut self, node_idx: NodeIndex) -> usize{
|
|
if self.nodes[node_idx].visited{
|
|
return 0;
|
|
}
|
|
|
|
let mut infected : usize = 1;
|
|
self.nodes[node_idx].visited = true;
|
|
|
|
let mut edge_index = self.nodes[node_idx].first_edge;
|
|
loop{
|
|
match edge_index{
|
|
None => break,
|
|
Some(idx) => {
|
|
let new_idx = self.edges[idx].target;
|
|
infected += self.dfs_backtrack(new_idx);
|
|
edge_index = self.edges[idx].next_edge;
|
|
},
|
|
}
|
|
};
|
|
|
|
return infected;
|
|
}
|
|
|
|
fn print(&self) -> String{
|
|
let mut string = String::new();
|
|
|
|
for (idx, node) in self.nodes.iter().enumerate(){
|
|
string.push_str(format!("Node{}\n{}", idx + 1, node).as_str());
|
|
}
|
|
|
|
string.push_str("\n\n\n");
|
|
for (idx, edge) in self.edges.iter().enumerate(){
|
|
string.push_str(format!("Edge{}\n{}", idx + 1, edge).as_str());
|
|
}
|
|
|
|
return string;
|
|
}
|
|
}
|
|
|
|
|
|
fn main(){
|
|
let num_nodes : NodeIndex = parse_line!(NodeIndex);
|
|
let num_edges : EdgeIndex = parse_line!(EdgeIndex);
|
|
let mut graph = Graph::new(num_nodes, num_edges);
|
|
|
|
for _i in 0..num_edges{
|
|
let (idx1, idx2) : (NodeIndex, NodeIndex) = parse_line!(NodeIndex, NodeIndex);
|
|
graph.add_edge(idx1 - 1, idx2 - 1);
|
|
graph.add_edge(idx2 - 1, idx1 - 1);
|
|
}
|
|
|
|
let infected : usize = graph.dfs(0);
|
|
println!("{}", infected);
|
|
}
|
|
|
|
|