Pagini recente » Cod sursa (job #747565) | Cod sursa (job #2329420) | Cod sursa (job #545452) | Cod sursa (job #810394) | Cod sursa (job #2924694)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void add(int x, int y, vector<int> adj[]){
adj[x].push_back(y);
}
void dfs_plus(int node, vector<int>&viz_plus, vector<int> adj[]){
viz_plus[node] = 1;
for(int i=0;i<adj[node].size();i++){
if(viz_plus[adj[node][i]] == 0)
dfs_plus(adj[node][i], viz_plus, adj);
}
}
void dfs_minus(int node, vector<int>&viz_minus, vector<int> adj[]){
viz_minus[node] = 1;
for(int i=0;i<adj[node].size();i++){
if(viz_minus[adj[node][i]] == 0)
dfs_minus(adj[node][i], viz_minus, adj);
}
}
int main(){
ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
long n,m;
fin>>n>>m;
vector<int> adj[n+1];
vector<int> transpose[n+1];
long x,y;
for(int i=0;i<m;i++)
{
fin>>x>>y;
add(x,y,adj);
add(y,x,transpose);
}
vector<int> viz_plus(n+1, 0);
vector<int> viz_minus(n+1, 0);
vector<int> componenta(n+1, 0);
int numar_componente = 0;
for(int i=1;i<=n;i++){
if(componenta[i] == 0)
{
for(int j=1;j<=n;j++){
viz_plus[j] = 0;
viz_minus[j] = 0;
}
numar_componente+=1;
dfs_plus(i, viz_plus, adj);
dfs_minus(i, viz_minus, transpose);
for(int j=1;j<=n;j++){
if(viz_plus[j] == 1 && viz_minus[j] == 1){
componenta[j] = numar_componente;
}
}
}
}
fout<<numar_componente<<endl;
for(int i=1;i<=numar_componente;i++)
{
for(int j=1;j<=n;j++)
{
if(componenta[j] == i){
fout<<j<<" ";
}
}
fout<<endl;
}
fin.close();
fout.close();
}