import System.Environment (getArgs)
import Data.List (sort, nub)
remdup
:: Eq a
=> [a
] -> [a
]remdup [] = []
remdup
(x:xs
) = x : remdup
(filter (/= x
) xs
)
-- Depth-first search to explore connected nodes
dfs graph node visited acc =
then acc
else let connectedNodes
= filter (\n
-> graph
!! node
!! n
== 1) [0..length graph
- 1] updatedVisited = node : visited
updatedAcc = node : acc
in foldr (\n acc
' -> dfs graph n updatedVisited acc') updatedAcc connectedNodes
-- Function to find connected components in the graph
connectedComponents
:: Graph
-> [[Int]]connectedComponents graph =
initialVisited = replicate nodes False
go [] _ connected = connected
go (node:nodes') visited connected =
if visited !! node
then go nodes' visited connected
else let component = dfs graph node [] []
updatedVisited
= foldr (\n v
-> v
++ [if n `
elem` component
then True
else False
]) visited
[0..nodes
- 1] in go nodes' updatedVisited (component : connected)
in reverse $ go [0..nodes - 1] initialVisited []
-- Function to parse input into adjacency matrix
parseInput :: String -> Graph
parseInput input = map (map read . words) (lines input)
-- Main function
main :: IO ()
main = do
args <- getArgs
case args of
[inputFile] -> do
contents <- readFile inputFile
let graph = parseInput contents
components = connectedComponents graph
uniqueComponents = nub (map remdup (map sort components)) -- Sort nodes within each component
putStrLn "Connected components:"
mapM_ print uniqueComponents
_ -> putStrLn "Usage: ./executable input_file"