Pagini recente » Cod sursa (job #2860986) | Cod sursa (job #1100181) | Cod sursa (job #2646712) | Cod sursa (job #2653698) | Cod sursa (job #767689)
Cod sursa(job #767689)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> order;
vector<bool> visited;
vector< vector<int> > adj;
vector< vector<int> > inv;
vector<int> compon;
vector<vector<int> > ccon;
int nrcomp;
void gen_inv(int n)
{
inv.resize(n+1);
for (int i=1;i<=n;i++)
{
for (int j=0;j<adj[i].size();j++)
{
inv[adj[i][j]].push_back(i);
}
}
}
void dfs_visit(int k,vector<vector<int> > &adj,int s=0 )
{
visited[k]= true;
if (s!=0){
compon[k] = s;
ccon[s].push_back(k);
}
for (int i=0;i<adj[k].size();i++)
{
if (!visited[adj[k][i]]){
dfs_visit(adj[k][i],adj,s);
}
}
order.push_back(k);
}
void dfs(int n, vector<vector<int> > &adj)
{
compon.resize(n+1);
for (int i=1;i<=n;i++)
{
if (!visited[i])
dfs_visit(i,adj);
}
}
void dfs2(int n, vector<vector<int> > &adj)
{
nrcomp=0;
compon.resize(n+1);
//order.resize(n+1);
ccon.resize(n+1);
for (int i=n-1;i>=0;i--)
{
if (!visited[order[i]]){
nrcomp++;
dfs_visit(order[i],adj,nrcomp);
}
}
}
int main()
{
FILE *f = fopen("ctc.in","r");
FILE *g = fopen("ctc.out","w+");
int n,m;
fscanf(f,"%d %d", &n,&m);
adj.resize(n+1);
for (int i=0;i<m;i++)
{
int x,y;
fscanf(f,"%d %d",&x,&y);
adj[x].push_back(y);
}
visited.resize(n+1);
for (int i=0;i<n;i++)
visited[i]= false;
dfs(n,adj);
gen_inv(n);
fill(visited.begin(),visited.end(),0);
dfs2(n,inv);
fprintf(g,"%d\n", nrcomp);
for (int i=1;i<=nrcomp;i++)
{
for (int j=0;j<ccon[i].size();j++)
{
fprintf(g,"%d ",ccon[i][j]);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
}