Pagini recente » Cod sursa (job #3123135) | Istoria paginii runda/oni-2015-cls11-12 | Cod sursa (job #1978563) | Cod sursa (job #851562) | Cod sursa (job #2967987)
#include<fstream>
#include<vector>
#include<stack>
#define pb push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 1e2 + 1;
vector<int> vecini[NMAX];
vector<int> ant[NMAX];
vector<bool> viz(NMAX),kosa(NMAX);
vector<int> compo[NMAX];
stack<int> stiva;
void dfs(int nod)
{
viz[nod] = 1;
for(auto v : vecini[nod])
{
if(!viz[v])
dfs(v);
}
stiva.push(nod);
}
void k(int nod,int nr)
{
kosa[nod] = 1;
for(auto it : ant[nod])
{
if(!kosa[it])
k(it,nr);
}
compo[nr].pb(nod);
}
int main()
{
int n,m,a,b,comp = 0;
cin >> n >> m;
for(int i = 0 ; i < m ; i++)
{
cin >> a >> b;
vecini[a].pb(b);
ant[b].pb(a);
}
for(int i = 1; i <= n ; i++)
{
if(!viz[i])
dfs(i);
}
// kosaraju
while(!stiva.empty())
{
int nod = stiva.top();
stiva.pop();
if(!kosa[nod])
{
k(nod,++comp);
}
}
cout << comp << '\n';
for(int i = 1; i <= comp ; i++)
{
for(auto it : compo[i])
{
cout << it << " ";
}
cout << '\n';
}
}