Hundreds of thousands of people who fled India's strongest cyclone in 14 years returned home to scenes of devastation Monday, as a massive relief operation kicked into gear.

Teams raced to restore power and other services after the cyclone struck India's eastern coast on Saturday, killing at least 22 people and leaving a trail of destruction.

Cyclone Phailin pounded the states of Orissa and Andhra Pradesh further south, bringing winds of more than 200 kilometres an hour (125 miles per hour), uprooting trees, overturning trucks, knocking out power lines and flooding farmland.

"The death toll from the cyclone in Orissa has now gone up from 17 to 21. The deaths are mostly due to falling walls and tree branches," Pradipta Kumar Mohapatra, the state's special relief commissioner, told AFP by phone. One person was also killed in Andhra Pradesh, officials said.

Casualties were minimised after one million people spent the night huddled in shelters, temples and schools during the ferocious storm, in what officials said was India's largest ever evacuation operation.

Indian President Pranab Mukherjee led a chorus of praise for the evacuation effort and the "high level of preparedness", as well as for the accurate forecasting of the country's weather bureaus.

Relief agencies said government officials seemed to have learnt the lessons from 1999, when a cyclone tore through the same region, killing more than 8,000 people and devastating crops and livestock.

"The government and the community were more aware this time and better prepared, it was a collective effort and a successful one," Manish Choudhary, a director of the Indian Red Cross Society, told AFP.

Officials in Orissa said 873,000 people moved before the cyclone made landfall on Saturday evening, while at least another 100,000 were evacuated in Andhra Pradesh. Residents were also evacuated from coastal regions of West Bengal state.

Many returned home on Monday to discover their homes -- often built just of flimsy mud and thatch -- as well as their businesses damaged or destroyed.

Mostly poor farmers and fishermen, they were resigned to getting on with the job of rebuilding rather than waiting for rescue workers.

"I left everything (behind) and when I came back nothing was here," said Bhagwan, 50, a coconut seller from the town of Gopalpur who uses one name, as he sat on the ground in front of his destroyed shop.

Kishor Nayak crammed into a boat with dozens of others to reach his village across a swollen river from Sunapur hamlet. Villagers clutched shoes, clothes, food and other basic possessions in plastic bags.

"My house is flat. I have to go back and fix it now," Nayak said.

"There is no food either. My kids have been starving, crying," he added.

Power infrastructure collapse

Some 3,000 officers from the National Disaster Response Force (NDRF) have fanned out across the region, a top official said.

"Our team is still working hard clearing roads, removing debris from damaged buildings and cutting and removing fallen electric poles and trees," NDRF director general Krishna Chaudhary told reporters.

Relief workers also distributed food at shelters, while authorities worked to restore power, water and other services. The army said 18 helicopters and 12 aircraft have been deployed to help with the relief operation.

The top official in the hardest-hit district of Ganjam said power services have been wrecked, while 500,000 homes in his district alone have been partially or completely destroyed.

"The power infrastructure has completely collapsed, it is smashed. There's no way electricity will be back tonight. It will take us a minimum of one week, maybe even two weeks to get power back," collector of Ganjam district Krishan Kumar said.

"Nothing is left here," he told AFP.

"About 30,000 people have lost their homes completely, they will stay in our cyclone shelters until they can rebuild," he added.

Choudhary, from the Red Cross, said 3,000 volunteers were distributing tents and other assistance to those left homeless, while the state government announced food assistance packages for affected families.

Although the cyclone has dissipated, heavy rain was falling across the region, with flood warnings in several districts in Orissa.

Meanwhile, the coastguard on Monday rescued 18 sailors -- 17 Chinese and an Indonesian -- who had been drifting on a lifeboat since their cargo ship started sinking on Saturday in the Bay of Bengal during the cyclone.

"The crew abandoned the ship and set out in a lifeboat after their vessel began sinking in the rough seas," coastguard Commandant Rajendra Nath told AFP from the city of Kolkata.

The lifeboat carrying the crew from MV Bingo was finally spotted overnight, drifting at the mouth of a river that runs into the bay near Orissa's Balasore city, said Nath, who led the operation.

The crew were taken to hospital in Kolkata for treatment, he said.

In another story of survival, 18 fishermen trapped offshore in rough seas abandoned their trawler as the cyclone approached, Nath said.

The fishermen swam to shore and were discovered before being taken to a local hospital near the port of Paradip in Orissa.

Some of the deadliest storms in history have formed in the Bay of Bengal, including one in 1970 that killed hundreds of thousands of people in modern-day Bangladesh.