Pagini recente » Rezultatele filtrării | Cod sursa (job #3294222)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> v[100001], reversed[100001],ans[100001];
stack<int> s;
int parc[100001],biconex[100001];
void dfs_normal(int node) {
parc[node] = 1;
for (int i=0;i<(int)v[node].size();++i) {
int node1 = v[node][i];
if (parc[node1] == 0)
dfs_normal(node1);
}
s.push(node);
}
void dfs(int node,int comp) {
parc[node] = 1;
biconex[node] = comp;
for (int i=0;i<(int)reversed[node].size();++i) {
int node1 = reversed[node][i];
if (parc[node1] == 0)
dfs(node1,comp);
}
}
int main() {
int i,j,k,n,m,x,y,node,comp=0;
fin>>n>>m;
for (i=1;i<=m;++i) {
fin>>x>>y;
v[x].push_back(y);
reversed[y].push_back(x);
}
for(i=1;i<=n;++i) {
if (parc[i]==0)
dfs_normal(i);
}
memset(parc,0,sizeof(parc));
while (s.size()!=0) {
node=s.top();
s.pop();
if(parc[node]==0)
dfs(node,++comp);
}
for(i=1;i<=n;++i) {
ans[biconex[i]].push_back(i);
}
fout<<comp<<'\n';
for(i=1;i<=comp;++i) {
for (j=0;j<(int)ans[i].size();++j) {
fout<<ans[i][j]<<" ";
}
fout<<'\n';
}
return 0;
}