Pagini recente » Cod sursa (job #2121713) | Cod sursa (job #2739060) | Cod sursa (job #1232081) | Cod sursa (job #3263880) | Cod sursa (job #2087110)
#include <bits/stdc++.h>
#define NM 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, nrc;
int Plus[NM], Minus[NM];
vector <int> G[NM], GT[NM], ctc[NM];
stack <int> st;
void df1(int x)
{
Plus[x] = 1;
for(int i=0; i < (int)G[x].size(); ++i)
if(Plus[G[x][i]] == 0)
df1(G[x][i]);
st.push(x);
}
void df2(int x) ///graful transpus
{
Minus[x] = nrc;
for(int i=0; i < (int)GT[x].size(); ++i)
if(Minus[GT[x][i]] == 0)
df2(GT[x][i]);
}
int main()
{
int i , j , m;
f >> n >> m;
while( m-- ) {
f >> i >> j;
G[i].push_back(j);
GT[j].push_back(i); ///graful transpus
}
for(int i=1; i <= n ; ++i)
if (Plus[i] == 0) df1(i);
while(!st.empty()){
int k = st.top();
st.pop();
if (Minus[k] == 0) {
nrc++;
df2(k);
}
}
for(int i=1; i <= n; ++i)
ctc[Minus[i]].push_back(i);
g << nrc << "\n";
for(int i=1; i <= nrc; ++i){
for(int j=0; j < (int) ctc[i].size(); ++j)
g << ctc[i][j] << " ";
g << '\n';
}
return 0;
}