Pagini recente » Cod sursa (job #1893546) | Cod sursa (job #1929883) | Cod sursa (job #1840961) | Cod sursa (job #400890) | Cod sursa (job #1174372)
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;
int N, M, sol;
vector<int> graph[100005], tgraph[100005];
vector<int> tsorted;
bitset<100005> visited;
vector<int> components[100005];
void bfs(int node);
void dfs(int node);
void tsort();
void tconex();
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
for (int i=0; i<M; ++i){
int from, to;
scanf("%d %d", &from, &to);
graph[from].push_back(to);
tgraph[to].push_back(from);
}
tsort();
tconex();
printf("%d\n", sol);
for (int i=0; i<sol; ++i){
for (unsigned j=0; j<components[i].size(); ++j)
printf("%d ", components[i][j]);
puts("");
}
return 0;
}
void bfs(int node){
components[sol].push_back(node);
for (unsigned i=0; i<components[sol].size(); ++i){
for (unsigned j=0; j<graph[components[sol][i]].size(); ++j){
if (visited[graph[components[sol][i]][j]]){
visited[graph[components[sol][i]][j]] = 0;
components[sol].push_back(graph[components[sol][i]][j]);
}
}
}
}
void dfs(int node){
for (unsigned i=0; i<tgraph[node].size(); ++i){
if (!visited[tgraph[node][i]]){
visited[tgraph[node][i]] = 1;
dfs(tgraph[node][i]);
}
}
tsorted.push_back(node);
}
void tsort(){
for (int i=1;i<=N; ++i){
if (!visited[i]){
visited[i] = 1;
dfs(i);
}
}
}
void tconex(){
for (int i=tsorted.size()-1; i>=0; --i){
if (visited[tsorted[i]]){
visited[tsorted[i]] = 0;
bfs(tsorted[i]);
++sol;
}
}
}