Pagini recente » Cod sursa (job #931660) | Cod sursa (job #2722825) | Cod sursa (job #1655135) | Cod sursa (job #507915) | Cod sursa (job #730533)
Cod sursa(job #730533)
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
typedef vector< vector<int> > Graph;
vector<int> explored, finish;
vector< vector<int> > sccs;
int cnt;
int how_many = 0;
void DFS1(Graph graph, int i)
{
explored[i] = 1;
for(int j=0; j<graph[i].size(); j++)
{
if(explored[graph[i][j]] == 0)
{
DFS1(graph, graph[i][j]);
}
}
finish[++cnt] = i;
}
void DFS2(Graph graph, int i)
{
explored[i] = 1;
sccs[how_many].push_back(i);
for(int j=0; j<graph[i].size(); j++)
{
if(explored[graph[i][j]] == 0)
{
DFS2(graph, graph[i][j]);
}
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int N, M, v1, v2;
scanf("%d %d", &N, &M);
Graph graph(N+1, vector<int>());
Graph reverse(N+1, vector<int>());
explored.resize(N+1);
finish.resize(N+1);
cnt = 0;
for(int i=0; i<M; i++)
{
scanf("%d %d", &v1, &v2);
graph[v1].push_back(v2);
reverse[v2].push_back(v1);
}
// reverse
for(int i=1; i<reverse.size(); i++)
{
if(explored[i] == 0)
{
DFS1(reverse, i);
}
}
// forward
for(int i=0; i<explored.size(); i++)
{
explored[i] = 0;
}
for(int i=N; i>0; i--)
{
if(explored[finish[i]] == 0)
{
sccs.push_back(vector<int>());
DFS2(graph, finish[i]);
how_many++;
}
}
cout << how_many << endl;
for(int x=0; x<sccs.size(); x++)
{
for(int y=0; y<sccs[x].size(); y++)
{
cout << sccs[x][y] << " ";
}
cout << endl;
}
return 0;
}