Pagini recente » Cod sursa (job #1747857) | Cod sursa (job #2669989) | Cod sursa (job #2528889) | Cod sursa (job #2062225) | Cod sursa (job #3213289)
#include <bits/stdc++.h>
using namespace std;
const int max_node = 1000;
vector<int> graph[max_node];
vector<int> transpose_graph[max_node];
vector<vector<int>>afis(100000);
bool vis[max_node];
int scc_count=0;
vector<int> node_order;
void dfs(int n){
if(vis[n]) return;
int len=graph[n].size();
vis[n]=true;
for(int i=0;i<len;i++)
dfs(graph[n][i]);
node_order.push_back(n);
}
void dfs_print(int n){
if(vis[n]==true) return;
afis[scc_count].push_back(n);
int len=transpose_graph[n].size();
vis[n]= true;
for(int i=0;i<len;i++)
dfs_print(transpose_graph[n][i]);
}
int kosarajuSCC(int n)
{
for(int i= 1; i<=n; i++)
if(vis[i] == false)
dfs(i);
for(int i= 1; i<=n; i++)
vis[i]= false;
for(int i= node_order.size()-1; i>= 1; i--)
{
if(vis[node_order[i]] == false)
{
dfs_print(node_order[i]);
scc_count++;
}
}
node_order.clear();
return scc_count;
}
int main(void)
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y;
fin>>n>>m;
for(int i= 0; i<= n; i++)
{
vis[i]= false;
graph[i].clear();
transpose_graph[i].clear();
}
for(int i=0;i<m;i++)
{
fin>>x>>y;
graph[x].push_back(y);
transpose_graph[y].push_back(x);
}
int components=kosarajuSCC(n);
fout<<components<<'\n';
for(int i=0;i<scc_count;i++,fout<<'\n')
for(int j=0;j<afis[i].size();++j)
fout<<afis[i][j]<<' ';
return 0;
}